Anonymous

用户名：Anonymouspledid

访问量：1375

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

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

　　作者: Anonymous　　　　发表时间：2020-02-15 17:52:17 浏览：1002　|　评论：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语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【亲和数】（C语言代码）

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

IP判断（C++代码）

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

评论区

精彩推荐

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

川哥的吩咐（C语言代码）

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

【明明的随机数】（C++代码）

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

蛇行矩阵（C语言代码）

1048题解（读入回车问题）

Hello, world! （C语言代码）

简单的a+b （C语言代码）

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

Anonymous

TA的其他文章

你可能喜欢

C二级辅导-同因查找 （C语言代码）

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

【亲和数】 （C语言代码）

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

IP判断 （C++代码）

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

评论区

精彩推荐

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

川哥的吩咐 （C语言代码）

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

【明明的随机数】 （C++代码）

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

蛇行矩阵 （C语言代码）

1048题解（读入回车问题）

Hello, world! （C语言代码）

简单的a+b （C语言代码）

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

C二级辅导-同因查找（C语言代码）

【亲和数】（C语言代码）

IP判断（C++代码）

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

　　评论区

川哥的吩咐（C语言代码）

【明明的随机数】（C++代码）

蛇行矩阵（C语言代码）