c语言网 1197 和UVa11292

295 阅读1分钟

贪心算法

c语言网 1197:发工资

输入

输入数据包含多个测试实例,每个测试实例的第一行是一个整数n(n<100),表示员工的人数,然后是n个员工的工资。 n=0表示输入的结束,不做处理。

输出

对于每个测试实例输出一个整数x,表示至少需要准备的人民币张数。每个输出占一行。

样例输入

3 1 2 3
0

样例输出

4
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int c[6]={100,50,10,5,2,1};
	freopen("1197.txt","r",stdin);
	int n;
	int money;
	while(scanf("%d",&n)&&n){
		int count=0;
		for(int i=0;i<n;i++){
			cin>>money;
			for(int j=0;j<6;j++){
				count=count+money/c[j]; 
				money=money%c[j]; 
			}
		}
		cout<<count<<"\n";	
	}
	return 0;
}

Uva 11292

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dragon[20005],knights[20005];
int main(){
	//freopen("11292.txt","r",stdin);
	int n,m;
	while(scanf("%d%d",&n,&m)==2&&n){
		//处理输入 
		memset(dragon,0,sizeof(dragon));
		memset(knights,0,sizeof(knights));
		for(int i=0;i<n;i++) cin>>dragon[i];
		for(int i=0;i<m;i++) cin>>knights[i];
		if(n>m){
			cout<<"Loowater is doomed!\n";
			continue;
		} 
		sort(dragon,dragon+n);
		sort(knights,knights+m);	
		int  coins=0,k=0,i=0;
		for(;i<n&&k<m;){
			if(dragon[i]>knights[k]){ // 骑士杀不掉龙 
				k++;   // 换下一个骑士 
			}else{    // 骑士能杀掉龙 
				coins+=knights[k];
				k++;     // 换下一个骑士 
				i++;       //  换下一条龙 
			} 
			
		}
		if(k<=m&&i==n)       //  如果龙被杀完 且骑士刚好或者没用用完 
			cout<<coins<<"\n";
		else{
			cout<<"Loowater is doomed!\n";
		}
		
	}
	return 0;
}