XYOJ1250导弹拦截问题(特殊输入+极限思想+双重循环）

题目描述

某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不 能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，因此1套系统可能不能拦截所有的导弹。

输入

输入数据只有一行，数据之间用空格隔开，表示导弹依次飞来的高度（<=100 枚，<=30000 ）。 输出

输出

一个数据，该数据表示若要拦截所有导弹至少要多少套这样的系统。

样例输入

300 150 120 540 360 471 140 364 146 340

样例输出

4

//这个建议参考心急的c小加 比它多考虑了一个a[j]!=0!!!(因为是小于等于而心急的c小加是大于等于，所以不需要考虑

str[j].w!=0) #include<stdio.h> int main() { int n,a[101],m=0; while(~scanf("%d",&n)) { a[m++]=n; if(getchar()=='\n') { //== break; } } int num=0; for(int i=0; i<m; i++) { if(a[i]!=0) { num++; for(int j=i+1; j<m; j++) { if(a[j]!=0&&a[j]<=a[i]) { //<= (1940心急的c小加是>=)所以要考虑a[j]!=0!!!!!!!!! a[i]=a[j];//一定不要忘 a[i]的值在变化！！！ a[j]=0;//把第二个for循环中符合的全部标记为0 } } // for(int i=0;i<m;i++){ // printf("%d ",a[i]); // } // printf("\n"); } } printf("%d\n",num); return 0; }

思想:用了两个数组，把b数组初始值都设为最大值，然后进行双重循环从前到后依次比较，看哪个b数组能容纳(大于等于）a数组的元素~

#include<stdio.h> int main(){ int n,m=0,a[101],b[101],num=0; while(~scanf("%d",&n)){ //特殊的输入~ a[m++]=n; if(getchar()=='\n'){ break; } } for(int j=0;j<m;j++){//<m b[j]=30000; } for(int i=0;i<m;i++){//核心~ for(int j=0;j<=i;j++){//依次比较 if(a[i]<=b[j]){ b[j]=a[i]; break;// } } } for(int j=0;j<m;j++){ if(b[j]!=30000){ num++; } } printf("%d\n",num); return 0; }