【作业】 贪心算法1

Tips:三题尚未完成。 

#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
int main(){
	int n,r,sum=0;
	cin>>n>>r;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a+0,a+n);
	for(int i=0;i<n;i++){
		if(i>=r){
			a[i]=a[i-r]+a[i];
		}
		sum+=a[i];
	}
	cout<<sum<<endl;
	
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
struct ACT{
	int st;
	int et;
};
ACT a[110];
bool cmp(ACT,ACT);
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].st>>a[i].et;
	}
	sort(a+0,a+n,cmp);
	int sum=1;
	int t=a[0].et;
	for(int i=1;i<n;i++){
		//cout<<a[i].st<<' '<<t<<' '<<(a[i].st<t)<<endl;
		if(a[i].st>=t){
			sum++;
			t=a[i].et;
		}
	}
	cout<<sum;
	return 0;
}
bool cmp(ACT a,ACT b){
	return a.et<b.et;
}

#include <iostream>
#include <algorithm>
using namespace std;
int mis[1010];
int demis[1010];
int demcnt=0;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>mis[i];
	}
	for(int i=0;i<n;i++){
		bool a=0;
		int b=-1;
		demis[b]=100000;
		for(int j=0;j<demcnt;j++){
			if(mis[i]<demis[j]&&demis[j]<demis[b]){
				a=1;
				b=j;
				demis[b]=mis[i];
			}
		}
		if(a==0){
			demis[demcnt]=mis[i];
			demcnt++;
		}
	}
	
	
	
	cout<<demcnt;
	return 0;
}
 

#include <iostream>
using namespace std;
int a[110][110]={0};
int main(){
	int n,ma=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			a[i][j]=a[i][j-1]+a[i][j];
		}
	}
	for(int j=1;j<=n;j++){
		for(int i=1;i<=n;i++){
			a[i][j]=a[i-1][j]+a[i][j];
		}
	}
	for(int sx=1;sx<=n;sx++){
		for(int sy=1;sy<=n;sy++){
			for(int ex=sx;ex<=n;ex++){
				for(int ey=sy;ey<=n;ey++){
					ma=max(ma,a[ex][ey]-a[ex][sy-1]-a[sx-1][ey]+a[sx-1][ey-1]);
				}
			}
		}
	}
	cout<<ma<<endl;
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
struct BQJ{
	int st;
	int ed;
};
bool cmp(BQJ a,BQJ b);
int main(){
	BQJ a[10100];
	int cnt=0,last=-5;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].st>>a[i].ed;
	}
	sort(a+0,a+n,cmp);
	for(int i=0;i<n;i++){
		if(last<a[i].st){
			last=a[i].ed;
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}
bool cmp(BQJ a,BQJ b){
	return a.ed<b.ed;
}

#include <iostream>
using namespace std;
int main(){
	int n;
	int x[1111];
	cin>>n;
	int sum=0;
	for(int i=0;i<n;i++){
		cin>>x[i];
		sum+=x[i];
	}
	int avg=sum/n;
	int cnt=0;
	for(int i=0;i<n;i++){
		if(x[i]!=avg){
			x[i]=avg;
			cnt++;
			x[i+1]=x[i+1]+(x[i]-avg);
		}
	}
	cout<<cnt;
	
	
	
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int mis[1010];
int demis[1010];
int misde[1010][1010];
int midcnt[1010]={0};
int demcnt=0;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>mis[i];
	}
	for(int i=0;i<n;i++){
		bool a=0;
		int b=-1;
		demis[b]=100000;
		for(int j=0;j<demcnt;j++){
			if(mis[i]<demis[j]&&demis[j]<demis[b]){
				a=1;
				b=j;
				demis[b]=mis[i];
				misde[b][midcnt[b]]=mis[i];
				midcnt[b]++;
			}
		}
		if(a==0){
			demis[demcnt]=mis[i];
			misde[demcnt][midcnt[demcnt]]=mis[i];
			midcnt[demcnt]++;
			demcnt++;
		}
	}
	cout<<demcnt<<endl;
	for(int i=0;i<demcnt;i++){
		cout<<i+1<<':';
		for(int j=0;j<midcnt[i];j++){
			cout<<misde[i][j]<<' ';
		}
		cout<<endl;
	}
	return 0;
}
 

#include <iostream>
#define _MAX 2147483647
using namespace std;
int tap[1100];
int stu[11000];
int ststa=0;
int mi=_MAX;
int m,n;
int t=0;
void func(int);
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>stu[i];
	}
	for(int i=0;i<m;i++){
		tap[i]=stu[i];
		mi=min(mi,tap[i]);
	}
	ststa=m;
	func(mi);
	cout<<t;
	return 0;
}
void func(int inc){
	int ma=0;
	mi=_MAX;
	t+=inc;
	for(int i=0;i<m;i++){
		tap[i]-=inc;
		if(tap[i]==0){
			tap[i]=stu[ststa];
			ststa++;
		}
		mi=min(mi,tap[i]);
		ma=max(ma,tap[i]);
	}
	if(ststa==n){
		t+=ma;
		return;
	}
	func(mi);
}