贪心

青藤 贪心（1）

网站: http://wikioi.cn/training/mission/10

第一题 排队接水

题目大意： 有n个人，给你每个人的装水时间，让你求最少平均等待时间。
分析： 让时间最少的排前面那么等待的时间就越少。
代码：

#include<bits/stdc++.h>
using namespace std;
int a[10000];
int main()
{
	long long n,ans=0;
	double sum;
	cin>>n;
	long long k=n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		ans+=a[i]*k;
		--k;
	}
	sum=ans*1.0/n;
	printf("%.2lf",sum);
	return 0;
}

第二题 删数问题

题目大意： 给你一个数和一个n，n表示你可以删几个数，让你求删n个数后最小的数。
分析： 用字符串读入，在判断删这个数是否比没删更好，就是这个数是否比后一个数小。如果是就删掉。
代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a;
	cin>>a;
	int s,len;
	cin>>s;
	len=a.size();
	for(int i=1;i<=s;i++)
	{
		if(len==0) break;
		int j=0;
		while(j+1<len && a[j]<=a[j+1]) j++;
		a.erase(j,1);
	}
	while(a.size()>0 && a[0]=='0') a.erase(0,1);
	if(a.size()==0) cout<<0;
	else cout<<a;
	return 0;
}

第三题 活动选择

题目大意： 给你一个n，就有n个活动，每个活动有开始时间和结束时间，让你求最多可以安排几个活动。
分析： 贪心排序最重要，这里排序是线段排序，看题意肯定是排右端点（结束时间），再用开始时间去比较，这个活动能不能排上。
代码：

#include<bits/stdc++.h>
using namespace std;
struct jg
{
	int b,e;
} a[1005];
bool cmp(jg a,jg b)
{
	return a.e<b.e;
}
int main()
{
	int n,last=0,ans=1;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].b>>a[i].e;
	sort(a+1,a+n+1,cmp);
	last=a[1].e;
	for(int i=2;i<=n;i++) 
	{
        if(a[i].b>=last)
		{
			ans++;
            last=a[i].e;
        }
    }
    cout<<ans<<endl;
	return 0;
}

第四题 最大整数

题目大意： 给你n个数，让你求这n个数拼接起来，让这个拼接的数最大。
分析： 还是用字符串读入，排序怎么排？这是用到了字符串的特性，两字符串数相加是拼在一起的，就可以这样判断 a+b>b+a 。最后一起输出。
代码：

#include<bits/stdc++.h>
using namespace std;
string a[100];
bool cmp(string a,string b)
{
	return a+b>b+a;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) cout<<a[i];
	return 0;
}

第五题 整数区间

题目大意： 给n个区间，形式为[a, b]，a和b均为整数，且a < b。求一个最小的整数点的集合，使得每个区间至少 1 个元素属于这个集合。求这个集合的元素个数。
分析： 这要确定一个最小的右边界，在判断比这个小的就行了。
代码：

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
int main()
{
    int T;
    cin>>T;
    for(int i=0;i<T;i++)
        cin>>a[i]>>b[i];
	sort(a,a+T-1);
    sort(b,b+T-1);
    int cnt=1;
    int temp=b[0];
    for(int i=1; i<T;i++)
    {
        if(temp<a[i]) 
        {
            cnt++;
            temp=b[i];
        }
    }
	cout<<cnt<<endl;
    return 0;
}

第六题 零件分组

题目大意： 给你n个零件的长度和重量，让你分出最少几组是使每一组的零件都能排成一个长度和重量都不下降的序列。
分析： 让可以组成序列的都在一个组，否则自创一个组。
代码：

**`#include<bits/stdc++.h>
using namespace std;
struct jg
{
	int w,l;
} a[1005];
bool cmp(jg a,jg b)
{
	if(a.l==b.l) return a.w<b.w;
	else return a.l<b.l;
}
bool f[1005];
int main()
{
	int n,ans=0,maxl,maxw;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].w;
	sort(a+1,a+n+1,cmp);
	maxl=a[1].l;
	maxw=a[1].w;

	for(int i=1;i<=n-1;i++)
	if (f[i] == false)
	{
		int cur = i;
		f[i] = true;
		ans ++;
		for(int j=i+1;j<=n;j++)
		{
			if(a[cur].l <= a[j].l && a[cur].w <= a[j].w && f[j] == false) {
				f[j] = true;
				cur = j;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}`

第七题 纪念品分组

题目大意： 给你n个纪念品的价格，分成每组，但每组价格不能超过m,和每个个数最多两个。
分析： 设置左边界和右边界，如果加起来小于m，那么左右边界减一，否则右边界减一。
代码：

#include<bits/stdc++.h>
using namespace std;
int a[30001];
int main()
{
	int mx,n,ans=0;
	cin>>mx>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	int l=1,r=n;
	while(l<=r)
	{
		if(a[l]+a[r]<=mx)
		{
			l++;
			r--;
		}
		else r--;
		ans++;
	}
	if(l==r)ans++;
	cout<<ans;
	return 0;
}

第八题 均分纸牌

题目大意： 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
分析： 如果是比平均少的找前面要，计数器加一。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[105],ans,s;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
    	cin>>a[i];
		ans+=a[i];
	}
    ans/=n;
    for(int i=1;i<=n;++i)
    {
        if(ans==a[i]) continue;
        a[i+1]+=a[i]-ans;
		s++;
    }
    cout<<s;
    return 0;
}

本文地址：https://blog.csdn.net/coollend/article/details/110205907