GESP4级考试语法知识(贪心算法(三))

拦截导弹代码:

#include<bits/stdc++.h>
using namespace std;

int a[1010],i,n,x,p,k,j; 
int main(){
	cin>>n;
	for(i=0;i<n;i++){
		cin>>x;//输入导弹高度 
		p=-1;  //做标记 
		for(j=1;j<=k;j++){ //循环判断是否能拉拦截 
			if(a[j]>x){
				p=j; 
				break;
			}
		}
		if(p==-1){//不能拦截 就开一个系统 
			k++;
			a[k]=x;
		}else{    //能拦截,就同步高度 
			a[p]=x;
		}
	}
	
	cout<<k;
}

活动选择代码:

#include <bits/stdc++.h> 
using namespace std; 

struct node                  //每个时间对 
{ 
 	int begin; 	
	int end; 
}; 
struct node a[110]; 
int n;  
bool cmp(node n1,node n2)   //按结束时间升序排序 
{ 	
	return n1.end < n2.end?true:false; 
}  
int main()
{ 
	int i; 
	cin>>n; 	
	for(i = 0; i < n; i++)
	{ 		
 		cin>>a[i].begin>>a[i].end; 	
	}  	
	sort(a,a+n,cmp);  	//第1个活动必选  	
	int ans=1; 	
	int t = a[0].end; 	//在剩余活动中选择  	
	for(int i=1; i<n; i++) 
	{ 		//如果当前活动与之前最后结束的活动不冲突,就接受当前活动。 		   
   		if(a[i].begin>=t) 
		{ 	
      		ans++; 			
      		t=a[i].end; 		
    	} 	
	} 	
	cout<<ans;
	return 0;
}

上一篇:【开源免费】基于Vue和SpringBoot的私人健身与教练预约管理系统(附论文)


下一篇:2024年9月青少年软件编程(C语言/C++)等级考试试卷(九级)