（周六赛1）最少拦截系统（题目都木有理解）

///转题意理解这个题目，有些人很容易被测试数据误解，这里用一个例子解释一下，50 40 60 10 30 理解错误会认为答案是3,其实应该是2，因为50 40 后虽然是60，但后面的30是可以接着40发射的，所以 50 40 30 60 10，总共是要2个。所以可以以一个数shuzu【i】开始，后面所有的数只要比shuzu【i】小，就将他们变成-1（以便后面不重复）；一次找到的所有高度就只需要一个系统就行了。 ————————————————————————————————————————————

话说我当时就完全误解题目了，太弱了T ^ T

Problem Description

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

怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

 1 #include<stdio.h>
 2 
 3 
 4 
 5 int main()
 6 
 7 {
 8 
 9 int n,i,j;
10 
11 int a[1000];
12 
13 while(~scanf("%d",&n))
14 
15 {
16 
17 for(i=0;i<n;i++)
18 
19 scanf("%d",&a[i]);
20 
21 int sum=0;
22 
23 for(i=0;i<n;i++)
24 
25 {
26 
27 if(a[i]!=-1)
28 
29 {
30 
31 int ok=a[i]; sum++;
32 
33 for(j=i+1;j<n;j++)
34 
35 {
36 
37 if(a[j]!=-1&&ok>a[j])
38 
39 {
40 
41 ok=a[j];
42 
43 a[j]=-1;
44 
45 }
46 
47 }
48 
49 }
50 
51 }
52 
53 printf("%d
",sum);
54 
55 }
56 
57 return 0;
58 
59 }

View Code