D:【基本算法—贪心算法】删数问题

描述

键盘输入一个高精度的正整数n（<=240位），去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案，使得剩下的数字组成的新数最小。

这道题目我们可以用贪心法则来攻克

既然要每次删除一个数，那我们就需要让每一次都做出一个最好的选择，这样最后我们也就会得到最佳方案

如何每一次都作出最好的选择，也就是每一次都删除第一个比后面数字大得数，因为如果n比n-1大的话，后面再出现此类情况，我们可以保证n在最大的数位上，于是这个步骤我们可以用函数来完成。

void del(){
	len=st.size();
	while(m--){
	int p=0;
	while(p<len-1&&st[p]<=st[p+1]) p++;
	st.erase(p,1);
	len--;
	}
}

这里面我们使用了搜索，由于只要没有找到满足条件的p，p就会++，所以p最后会停在满足条件数的前一位
但是如果找不到满足条件的数字，我们就应该删掉最高位的那一个数字
下面我们应该做的事情就是删除前导零，我们依旧可以用搜索完成，p将会停留在第一个不为零的数字上

void pri(){
	int p=0;
	while(p<len-1&&st[p]==‘0‘){
	p++;
}
	for(int i=p;i<len;i++)
	cout<<st[i];
}

 

F:〖NOIP2008P〗排座椅

描述

上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来 之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i,j），为了方便同学们进出，在教室中设 置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通 道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。

这道题也应该是一道贪心算法，因为我们要在有限的改变次数内做出最好的选择。

怎么样才能算是最好选择？

如果我们要在行之间隔出一条通道，那么我们就应该选择两行之间交头接耳人数最多的，在这里开一条通道

如果我们要在列之间隔出一条通道，那么我们就应该选择两列之间交头接耳人数最多的，在这里开一条通道

于是我们需要对每两行和每两列之间交头接耳的人做出排序，并且记录下他们的位置，然后进行选择

void readp(){
     cin>>n>>m>>nk>>mk>>d;
     for(int i=1;i<n;i++) h[i].id=i;
     for(int i=1;i<m;i++) l[i].id=i;
     int x1,y1,x2,y2;
     while(d--){
           cin>>x1>>y1>>x2>>y2;
           if(x1==x2) {
              if(y1<y2) l[y1].s++;
              else l[y2].s++;
              }
              else {
                   if(x1<x2) h[x1].s++;
                   else h[x2].s++;
                  }
           }
     }
    读入并且记录下每行每列交头接耳的人数，记录下行号和列号

void work(){
     sort(h+1,h+n,cmp);
     sort(l+1,l+m,cmp);
     sort(h+1,h+nk+1,cmp1);
     sort(l+1,l+mk+1,cmp1);
     for(int i=1;i<=nk;i++) cout<<h[i].id<<" ";
     cout<<endl;
     for(int i=1;i<=mk;i++) cout<<l[i].id<<" ";
     cout<<endl;
}
把人数排序，并且由于输出也需要排序，所以我们还要使用函数对结构体进行排序

bool cmp(node p,node q){
     return p.s>q.s;
}

bool cmp1(node p,node q){
     return p.id<q.id;
}

B:〖NOIP2010P〗导弹拦截

描述

经过11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0   时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径 的平方和。
某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

只做出了40分的程序

这道题其实就是两个系统工作的最短半径，也就是必定会有导弹刚好落到这两个系统的边缘上，并且没有遗漏，否则这个半径一定可以继续缩短。

通过提示，我们知道可以利用半径的平方和比较大小

int dis(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

然后我们需要进行读入

void readp(){
     cin>>a>>b>>c>>d;
     cin>>n;
     for(int i=1;i<=n;i++)
     cin>>x[i]>>y[i];
}

接着就是要计算出每一次的平方和，然后比较大小，输出最小的那一个

void work(){
     int minv=10000000;
     for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++){
     int r1=dis(a,b,x[i],y[i]);
     int r2=0;
     for(int k=1;k<=n;k++) 
     if(dis(a,b,x[k],y[k])>r1&&dis(c,d,x[k],y[k])>r2)
     r2=dis(c,d,x[k],y[k]);
     if(minv>r1+r2) minv=r1+r2;
     }
     cout<<minv;
}
当然这个程序只能得到40分，因为它使用了三层循环