【例4】均分纸牌（NOIP2002）
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 N=4，4 堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6
移动3次可达到目的：
从 ③ 取4张牌放到④（9 8 13 10）->从③取3张牌放到 ②（9 11 10 10）-> 从②取1张牌放到①（10 10 10 10）。
【输入格式】
N（N 堆纸牌，1 <= N <= 100）
A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
【输出格式】
所有堆均达到相等时的最少移动次数。
【样例输入】Playcard.in
4
9 8 17 6
【样例输出】Playcard.out
3
1 #include <stdio.h> 2 int main() 3 { 4 int i,n,a[105],sum=0; 5 scanf("%d",&n); //输入纸牌堆数 6 for(i=1;i<=n;i++)//输入各堆牌数 弃置0堆 7 { 8 scanf("%d",&a[i]); 9 sum+=a[i]; 10 } 11 sum/=n;//求平均数 12 for(i=1;i<=n;i++) 13 a[i]-=sum; 14 //极端情况出现 0 0 0 x x 0 x x 0 0 x 0 0 0 0这种 15 //现在就见0直接往前挪 不是0把牌丢给右边 负数相当于逆向移牌 16 //如-3移到1变成0 -2，相当于1移3张给-3 17 i=1; 18 sum=0; 19 while(i<=n) 20 { 21 if(a[i]==0) 22 { 23 i++; 24 } 25 else 26 { 27 a[i+1]+=a[i]; 28 a[i]=0; 29 i++; 30 sum++; 31 } 32 } 33 printf("%d",sum); 34 return 0; 35 }
【例5】删数问题（NOI94）
输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。
输出新的正整数。（N不超过240位）输入数据均不需判错。
【输入】
n
s
【输出】
最后剩下的最小数。
【样例输入】
175438
4
【样例输出】
13
【算法分析】
由于正整数n的有效数位为240位，所以很自然地采用字符串类型存贮n。那么如何决定哪s位被删除呢？是不是最大的s个数字呢？显然不是，大家很容易举出一些反例。为了尽可能逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符，这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个数字。重复以上过程s次为止，剩下的数字串便是问题的解了。
1 #include <stdio.h> 2 #include <string.h> 3 int main() 4 { 5 char a[250]; //存长数 6 int s,len,k,i=0; //i为当前选择的位置 7 scanf("%s",a); 8 scanf("%d",&s); 9 len=strlen(a); 10 11 while(a[i]=='0') i++; //去除首0 12 //我们现在举个例子，2293620，删4次 13 //原理是删第一个单调子段的最大数 14 //第一个单调子段【相等也视为单调】 229 15 //删掉9 -> 223620 16 //删掉3 -> 22620 17 //删掉6 -> 2220 18 //删掉第一个2 -> 220 19 //整个过程就是这样 20 while(s--) 21 { 22 if(a[i]>a[i+1]) //如果是单调递减子段，直接删第一个 23 { 24 i++; 25 } 26 else if(a[i]<=a[i+1]) //单调递增子段查找最后一个字符，注意用<= 27 { 28 k=i+1; //i不动，k去找 29 while(a[k]<=a[k+1]) k++; //这个k最终到达末尾 30 while(k+1<len) //从前往后挪，挪到最后一个数是k+1 31 { 32 a[k]=a[k+1]; 33 k++; 34 } 35 len--; //减少字符长度 36 } 37 } 38 for(;i<len;i++) 39 printf("%c",a[i]); 40 41 return 0; 42 }
【例6】拦截导弹问题（NOIP1999）
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。
【输入格式】
n颗依次飞来的高度（1≤n≤1000）.
【输出格式】
要拦截所有导弹最小配备的系统数k。
【输入样例】missile.in
389 207 155 300 299 170 158 65
【输出样例】missile.out
2
【输入输出样例】
输入：导弹高度： 7 9 6 8 5
输出：导弹拦截系统K=2
输入：导弹高度： 4 3 2
输出：导弹拦截系统K=1
1 #include <stdio.h> 2 int main() 3 { 4 // freopen("missile.in","r",stdin); 5 // freopen("missile.out","w",stdout); 6 int flag,sumj=1,height,jacket[1005],i; 7 scanf("%d",&height); 8 jacket[0]=height;//先把第一个导弹拦截下来 9 while(scanf("%d",&height)==1)//你懂的 10 { 11 flag=1; 12 for(i=0;i<sumj;i++) 13 { 14 if(jacket[i]==height) break;//如果有遇到高度相同自然是不用再准备一套的 15 else if(jacket[i]>height)//一个一个找，找到就降低高度并跳出 16 { 17 jacket[i]=height; 18 flag=0; 19 break; 20 } 21 } 22 if(flag) //如果上面都没找到就准备新的导弹 23 { 24 sumj++; 25 jacket[i]=height; 26 } 27 } 28 printf("%d",sumj); 29 return 0; 30 }
这个算法确保了，如果存在一个能拦截此导弹的装置，那么这个装置是所有可拦截装置中高度最小的一个。