Anonymous

用户名：Anonymouspledid

访问量：1436

签　名：

等　　级
排　　名	10086
经　　验	1111
参赛次数	6
文章发表	1
年　　龄	0
在职情况	学生
学　　校	中国科学技术大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-拦截导弹（C++代码）贪心
浏览：1049

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

蓝桥杯算法训练VIP-拦截导弹（C++代码）贪心

　　作者: Anonymous　　　　发表时间：2020-02-15 17:52:17 浏览：1049　|　评论：1　

原题链接：蓝桥杯算法训练VIP-拦截导弹

#贪心算法
这个算法相比其他的时间复杂度更高，但是更好想。
贪心的想法：每次把一个系统能清除的导弹全部清除，直到导弹数为0.
```cpp
#include<vector>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int>a;
struct link{
	int val;
	int next;//next 用来记录这条子串里下一个点的下标 val即为子串长度
};
vector<link>lis;//记录最长递增子串
int main(){
	int cnt=0,num=0,n;
//	cin>>n;
	int x;
	while(cin>>x){
		a.push_back(30000-x);//原题应求递减，个人喜好改成了递增
		num++;
	}
	n=num;
	while(!a.empty()){
		cnt++;
		lis.clear();
		for(int i=0;i<n;i++){
			lis.push_back({1,i});//初始化lis数组
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<i;j++){
				if(a[j]<a[i]){
					if(lis[j].val+1>lis[i].val){
						lis[i]={lis[j].val+1,j};
					}
				}
			}
		}
		int m=0,pos=0;
		for(int i=0;i<n;i++){
			if(lis[i].val>m){
				m=lis[i].val;
				pos=i;
			}
		}
		if(cnt==1){
			cout<<m<<" ";
		}
		while(lis[pos].next!=pos){
//			cout<<30000-a[pos]<<" "; 
			a.erase(a.begin()+pos); //反序删点
			pos=lis[pos].next;
		}
//		cout<<30000-a[pos]<<endl;
		a.erase(a.begin()+pos); 
		n=a.size();
	}
	cout<<cnt<<endl;
	return 0;
}
```
```

0.0分

13 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

shiren

while(cin>>x){
        a.push_back(30000-x);//原题应求递减，个人喜好改成了递增
        num++;
    }
怎么跳出循环啊

2021-04-14 13:37:12

Anonymous

TA的其他文章

你可能喜欢

汽水瓶（C语言代码）

C语言训练-舍罕王的失算（C语言代码）

C二级辅导-计负均正（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

蓝桥杯算法训练VIP-拦截导弹（C++代码）贪心

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

计算质因子（C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1013题解

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）简单循环

世界杯来了

Anonymous

TA的其他文章

你可能喜欢

汽水瓶 （C语言代码）

C语言训练-舍罕王的失算 （C语言代码）

C二级辅导-计负均正 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

蓝桥杯算法训练VIP-拦截导弹 （C++代码）贪心

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

计算质因子 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1013题解

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）简单循环

世界杯来了

汽水瓶（C语言代码）

C语言训练-舍罕王的失算（C语言代码）

C二级辅导-计负均正（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

蓝桥杯算法训练VIP-拦截导弹（C++代码）贪心

　　评论区

计算质因子（C++代码）