HDU 1257 最少攔截系統(tǒng)
來源：程序員人生 發(fā)布時間：2014-09-09 23:19:50 閱讀次數(shù)：2116次
http://acm.hdu.edu.cn/showproblem.php?pid=1257
題目大意：
有一種導彈攔截系統(tǒng)，每次只能發(fā)射比前一發(fā)導彈低的炮彈，給定一些導彈的襲擊順序，求至少需要多少導彈攔截系統(tǒng)來完全阻止
思路：
好久沒做題。做題水的~
直接模擬即可~
#include<cstdio>
const int MAXN = 30000 + 10;
const int INF = 0x3ffffff;
int a[MAXN], ans;
int cur_max[MAXN]; //當前導彈系統(tǒng)能達到的最大高度
int main()
{
int n;
while (~scanf("%d", &n))
{
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
ans = 1;
cur_max[0] = a[0];
for (int i = 1; i < n; i++)
{
int dis_min = INF;
for (int j = 0; j < ans; j++)
{
//當當前導彈小于某個可以攔截的導彈系統(tǒng)時候
//查找最接近這個導彈高度的
if (a[i] < cur_max[j] && dis_min > cur_max[j])
dis_min = j;
}
if (dis_min == INF)
dis_min = ans++;
cur_max[dis_min] = a[i];
}
printf("%d
", ans);
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
