题目分析
noip老经典贪心问题了 使用贪心策略，现在对于导弹i，和已经存在的k个系统，导弹i现在面临两种情况。 1、加入已存在的k个系统之中的一个系统之中。 当然前提条件是至少比其中一个系统的最小值小，那么如何用更少的系统，去装下更多的导弹呢？导弹i当然要选择能加入的导弹最小值的距离最近的，这样系统里的导弹才能更加的紧凑，不浪费空间。局部贪心导致最优解。 2、无法加入已存在的任何一个系统 新开辟一个系统。
code:
#include<bits/stdc++.h>
typedef long long ll
;
using namespace std
;
int arr
[1005];
int l
[1005];
int main()
{
int x
,k
=1,n
=0;
while (cin
>> x
)
{
arr
[++n
] = x
;
}
l
[k
] = arr
[1];
for (int i
= 2; i
<= n
; i
++)
{
int p
= 0;
for (int j
= 1; j
<= k
; j
++)
{
if (l
[j
] >= arr
[i
])
{
if (p
== 0)
{
p
= j
;
}
else if (l
[j
]< l
[p
])
{
p
= j
;
}
}
}
if (p
== 0)
{
l
[++k
] = arr
[i
];
}
else
{
l
[p
] = arr
[i
];
}
}
cout
<< k
;
}
