貪心訓練日記

1.陶陶摘蘋果luoguP1478

貪心

貪心假設：在所有可以摘到的蘋果中，優先選擇需要力氣小的蘋果。

貪心證明：因為要求的是共能摘多少個蘋果，是以我們可以将每個蘋果的價值都視為1。那麼無論是摘比較費勁的蘋果還是比較省力的蘋果所得到的價值都是一樣的。但如果摘比較省力的蘋果，就可以留下更多的力氣去摘其他的蘋果。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5100;
int n;
int s;
int a,b;
int y[N],idx=1;

int main(){
	cin>>n>>s>>a>>b;
	for (int i=1;i<=n;i++){
		int high,force;
		cin>>high>>force;
		if (a+b>=high) y[idx++]=force; 	
	}
	sort(y+1,y+idx);
	int ans=0;
	
	for (int i=1;i<idx;i++){
		s-=y[i];
		if (s>=0)
			ans++;
		 
		else	
			break;
	}
	cout<<ans<<endl;
	return 0;
}

           

2. luoguP1610鴻山洞的燈

貪心

貪心假設：将是以燈按照坐标由小到大排序後，隻要有符合條件的燈就将它關閉。

貪心證明：由于已經排完序，是以燈的坐标單調遞增。設目前燈i可關閉,i+1也可以關閉,且如果關閉i，則i+1無法關閉，如果關閉i+1,則i無法關閉。那麼由于i+1的坐标更靠後，i+1比i更容易滿足讓其它燈可以關閉的條件。且i與i+1的價值一樣(都會使答案+1)，是以i+1比i更優，是以應關閉第i盞燈。

#include<bits/stdc++.h>
using namespace std;
int n,dist,a[100002],sum;
int main()
{
	cin>>n>>dist;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=2; i<=n-1; i++)
	{
		if(a[i+1]-a[i-1]<=dist)
		{
			a[i]=a[i-1];    
			sum++;
		}
	}
	cout<<sum<<endl;
	return 0;
}

           

3. luoguP1115最大字段和

字首和思想+貪心

貪心假設：設sum為目前字段和，ans為目前最大子段和。每輸入一個數，sum的值就加上這個數，如果這個數比ans大的話，就将ans更新為sum。判斷過後，如果sum<0，則将sum重置為0。(意為重新開始選擇一個區間)。

貪心證明：

因為對于每一個sum，我們都在判斷其是否<0之前，判斷了其是否可以更新ans，是以如果我們可以周遊到是以可行的方案，那麼該貪心做法就是成立的。如果sum<0，sum無論是加一個正數還是一個負數，都會是加上的數的值變小，是以不利于ans變大。如果ans>=0那麼ans加上一個數，最終得到的值一定會比，加上的數的原數大，更加利于ans變大。

Tip:由于<0的數加上任何數，都會使這個數變小，>0的數加上任何數，都會使這個數變大，是以0常常作為貪心問題中取舍的分界線。

#include <bits/stdc++.h>
using namespace std;
int n,ans,sum,now;
int main()
{
    scanf("%d",&n);
    scanf("%d",&now);
    ans=now;
    if(now>0) sum=now;
    for(register int i=2;i<=n;i++)
    {
        scanf("%d",&now);
        sum+=now;
        if(sum>ans) ans=sum;
        if(sum<0) sum=0;
    }
    printf("%d",ans);
    return 0;
}