[数据结构与算法]贪心题集汇总

贪心

P3817 小A的糖果

题意：
数列相邻两个数的和不能大于x，每次进行的操作可以-1,问最少进行多少次操作使数列符合条件

思路：
从第一个元素开始往后模拟分析。cnt记录操作次数
如果a[1]+a[2]>x，我们需要对其中一个数字进行减法操作，对那个数字减呢？——第一个数字只会和第二个数字组成一对，但是第二个数字还会和第三个数字组成一对，所以我们对第二个数字进行操作cnt+=x-a[2]-a[1]，这样还可以同时减小后面一组的总数。
后面的所有组都类推，我们每次都只对每一组的第二个数字进行操作。记录操作次数

为了让操作数尽可能的小，如果a[i]+a[i+1]>x，我们只需要减第二个数到a[i]+a[i+1]=x即可，即a[i+1]=x-a[i]

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,x,a[N];
int main()
{
	cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i];
    LL cnt=0;
    for(int i=1;i<n;i++)
    {
        LL sum=a[i]+a[i+1]-x;
        if(sum>0)
        {
            cnt+=sum;
            a[i+1]=x-a[i];
        }
    }
    cout<<cnt<<endl;
	return 0;
}

P5019 [NOIP2018 提高组] 铺设道路

链接

思路：

从左到右每次找到a[i+1]>a[i]的情况，然后a[i+1]-a[i]就是在遇到下一个最大的数之前，这一字段全变成0需要的次数。所以每次找到a[i+1]-a[i]的情况，cnt+=a[i+1]-a[i]

分析：

相当于把一个字符串分为好几个字串，以较大数字为分割。

6   
4 3 2 5 3 5 
分割为：
4 3 2
5 3
5

我们每次可以选一个区间[l,r]对区间内的数字-1，前面大的数字-1会带动后面的数字也-1，所以只需要对子段中最大的数字进行处理，后面如果较小的数字提前变成0，相当于将区间[l,r]缩小了，但仍然是减最大的数字，并且贪心，每次从最左边开始对a[i+1]>a[i]的数字进行操作时，后面所有的数字都会跟着-1，并且真正决定每个大数减到0的操作数的是他前面的小数字，所以每个大数进行的操作是a[i+1]-a[i]

#include <iostream>
#include <algorithm>
using namespace std;

constexpr int N = 1e5 + 100;
int a[N], n;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	
	int sum = 0;
	for (int i = 0; i < n; i++)
		 if (a[i] < a[i + 1]) sum += a[i + 1] - a[i];
		 
	cout << sum << '\n';
	
	return 0;
}

E 动作游戏

链接

#include<iostream>
#include<algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII>p,ans;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,t;
    cin>>n>>t;
    for(int i=0;i<n;i++) 
    {
        int l,r;
        cin>>l>>r;
        p.push_back({l, r});
    }
    sort(p.begin(),p.end());

    int st=-2e9,ed=-2e9;
    for(int i=0;i<p.size();i++)
    {
        if(p[i].first>=ed)
        {
            if(st!=-2e9) ans.push_back(make_pair(st,ed));
            st=p[i].first,ed=p[i].second;
        } 
        else ed=max(ed,p[i].second);
    }
    if(ed!=-2e9) ans.push_back({st,ed});


    int last=0,flag=1,x=ans[0].first;
    for(int i=0;i<ans.size();i++)
    {
        if((ans[i].second-ans[i].first)>t){ flag=0; break; }
        if(last>ans[i].first&&last<ans[i].second)
        {
            if((last-ans[i].first)<=x) last=ans[i].first;
            else {flag=0; break;}
        }
        x=ans[i].first-last;
        last=max(last+t,ans[i].first+t);
    }
    if(flag) puts("HEIR OF FIRE DESTORYED.");
    else puts("YOU DIED.");
	return 0;
}

(同类题)B. Take Your Places!

链接
贪心，贪心思路对了就很好想了。首先，判断无法成立很容易，如果是偶数个元素，判断是否奇偶数各占一半，如果是奇数个元素，判断是否奇数比偶数多 1 或者少 1。如果无法成立，则输出?1。
否则，我们只需要考虑两种情况

1. 第一个元素是奇数。
2. 第一个元素是偶数。
   也就是说，我们最后的数组一定是 10101，或者 01010这样的( 1看成奇数， 0看成偶数)。我们可以将当前数组的奇数位置存储下来，如果数组总个数 $n$为奇数，那么如果奇数多就将奇数放在奇数位置，奇数少就将奇数放在偶数位置，依次放入，暴力求移动次数。如果数组总个数$n$为偶数，那么奇数放在奇数位置算一次，奇数放在偶数位置也算一次移动次数，取$min$即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int N=1e5+100,INF=0x3f3f3f3f;
int a[N];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		vector<int>odd;
		for(int i=1;i<=n;i++)
		{
			int c;
			cin>>c;
			if(c%2) odd.push_back(i);
		}
		if((n%2==0&&odd.size()*2!=n)||(n%2&&odd.size()*2!=n+1&&odd.size()*2!=n-1))
		{
			puts("-1");
			continue;
		}
		//if(n==1){puts("0");continue;}
		
		int ans=0;//奇数放在奇数位置，需要移动的次数
		int res=0;//奇数放在偶数位置，需要移动的次数
		if(n%2==0)
		{
			for(int i=0,k=1;i<odd.size();i++,k+=2)
			ans+=abs(odd[i]-k);
			
			for(int i=0,k=2;i<odd.size();i++,k+=2)
			res+=abs(odd[i]-k);
			
			ans=min(res,ans);//取两种可能中的最小值为答案
		}else
		{
			if(odd.size()*2==n+1)
			{
				for(int i=0,k=1;i<odd.size();i++,k+=2)
				ans+=abs(odd[i]-k);
			}else
			{
				for(int i=0,k=2;i<odd.size();i++,k+=2)
				ans+=abs(odd[i]-k);
			}
		}
		cout<<ans<<endl;

	}
}

P1106 删数问题

观察样例，每次删除a[i]>a[i+1]的数字

别忘了去掉前导0！！！

#include<iostream>
#include<algorithm>
using namespace std;
const int N=300;
int a[N];
int main()
{
	string s;
	cin>>s;
	int k;
	cin>>k;
	for(int i=0;i<s.size();i++)
	a[i]=s[i]-'0';
	
	int len=s.size();

	while(k--)//k次缩短长度
	{
		for(int i=0;i<len-1;i++)
		{
			if(a[i]>a[i+1])
			{
				for(int j=i;j<len;j++)//后面的数字前移，相当于删掉这个数字
				a[j]=a[j+1];
				break;
			}
		}
		len--;		
	}
	
	//去掉前导0
	int j=0;
	while(len>1&&a[j]==0) j++;//这里不能len--，因为0不算长度
	
	//从不是前导0的地方开始输出
	for(int i=j;i<len;i++)
	cout<<a[i];
	puts("");
	
	
	
	return 0;
}

P4995 跳跳！

0，大，小，大，小····

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=310;
int h[N];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>h[i];
	
	sort(h+1,h+n+1);
	
	long long sum=0;
	int l=0,r=n;
	while(l<r)
	{
		sum+=pow(h[l]-h[r],2);//先从小跳向大（大左边的小数）
		l++;//右移到下一小数（大右边的小数）
		sum+=pow(h[l]-h[r],2);//再从大跳向小(大会用到两次)
		r--;
	}
	
	cout<<sum<<endl;
	
	
	return 0;
}