注册了域名怎么做网站,制作图片库,免费下载的app,福州免费企业建站题目描述
某国为了防御敌国的导弹袭击#xff0c;发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷#xff1a;虽然它的第一发炮弹能够到达任意的高度#xff0c;但是以后每一发炮弹都不能高于前一发的高度。某天#xff0c;雷达捕捉到敌国的导弹来袭。由于该系统…题目描述
某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度雷达给出的高度数据是≤50000 \le 50000≤50000的正整数计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式 1行若干个整数个数≤100000 \le 100000≤100000
输出格式 2行每行一个整数第一个数字表示这套系统最多能拦截多少导弹第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出样例 输入 #1 389 207 155 300 299 170 158 65
输出 #1 6 2
解析
第一问相当于最长不上升子序列 第二问是贪心的思想
代码
#includecstdio
#includecmath
#includecstring
#includealgorithm
using namespace std;
int tot1;
int x[100005];
int main(){while(scanf(%d,x[tot])!EOF){mxmax(mx,x[tot]);tot;}tot--;int q[100005]{ },num10;for(int i1;itot;i){if(q[num1]x[i]||num10){q[num1]x[i];continue;}int ans;for(ans1;ansnum1;ans){if(q[ans]x[i]) break;/*这里没有等号使结尾的min尽可能的大后面的元素才能尽可能的可以放到队尾从而使队列最长*/ }q[ans]x[i];}int num0;for(int i1;itot;i){if(q[num]x[i]){q[num]x[i];continue;}int st1,ednum,mid,ansed;for(ans1;ansnum;ans){if(q[ans]x[i]) break;/*这里与上一问相比多个等号使结尾的max尽可能的大后面才能尽可能的不需要增加一组*/ }q[ans]x[i];}printf(%d\n%d,num1,num);
}
