最少拦截系统 

Time Limit:1000MS  Memory Limit:32768K

Description:

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度。某天,雷达捕捉到敌国的导弹来袭，因为该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊。所以俺就到这里来求救了，请帮助计算一下最少需要多少套拦截系统呢？

 

Input:

输入若干组数据。每组数据包括：导弹总个数(正整数)，导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，用空格分隔）。

Output:

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

Sample Input:

8 389  207  155  300  299  170  158  65

Sample Output:

2 code :

1 /* 2 不用特意寻找向量中的差值最小的，因为此题中，向量中的数必定是按升序排列的，只需从前往后比较饥渴。  3 */ 4 #include 
       
         5 #include 
        
          6 using namespace std; 7  8 int main() 9 {10     for (int n; cin >> n;) {11         int i;12         vector
         
           ve;13         for (i = 0; i < n; i++) {14             int m;15             cin >> m;16             int k = -1;17             for (int j = 0; j < ve.size(); j++) {18                 if (ve[j] >= m) {19                     k = j;20                     break;21                 }22             }23             if (k > -1) {24                 ve[k] = m;25             }26             else {27                 ve.push_back(m);28             }29         }30         cout << ve.size() << endl;31     }32 }