回顾-贪心

洛谷1090 合并果子
题意·：把两堆放到一堆花费两堆的和体力，将所有堆最后合成一个堆，求最小体力
分析：贪心寻找最小挪法，每次将最小的两堆合在一起
写法1
这个开始ac的后来看题解不晓得为啥能过，大概是数据太弱，大家直接看2把

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>

using namespace std;

const int N = 1e5+10;
int n,sum=0;
int a[N];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);

    for(int i=0;i<n-1;i++)
    {
        sort(a+i,a+n);//每次找最小两个
        int x=a[i]+a[i+1];
        sum+=x;
        a[i+1]=x;
    }
    printf("%d\n",sum);
    return 0;
}

写法2

使用优先队列，非常简单，但是数据大的话可能过不了
每次取最前面的两个数也就是最小

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>

using namespace std;

int n,sum=0;
priority_queue<int,vector<int>,greater<int> >q;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        q.push(x);
    }
    for(int i=0;i<n-1;i++)
    {
        int a=q.top();q.pop();
        int b=q.top();q.pop();
        sum+=a+b;
        q.push(a+b);
    }
    printf("%d\n",sum);
    return 0;
}

洛谷 7427 玩游戏

题意：两个人比分为a和b 能不能在n个回合达到这个分数（i回合硬，加i分）
分析：先判断是不是能达到a和b的分数的和 1~n的和 等差数列求和
sum=n(n+1)/2* 若可以得到分数，则贪心求出第一个人赢的回合，从大到小寻找 避免回溯

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

//开 long long

long long a,b;
long long sum=0;

int main()
{
    scanf("%lld%lld",&a,&b);

    long long n=sqrt(2*(a+b));

    if(n*(n+1)!=2*(a+b))printf("No\n");//1~n求和 判断是否存在
    else
    {
        printf("%lld",n);
        for(long long i=n;a;i--)//从大到小寻找 避免回溯
        {
            if(i<=a)
            {
                a-=i;
                printf(" %lld",i);
            }
        }
    }

}

P1684 考验
题意： 每段四行诗的韵脚只可能是“AABB”, “ABAB”, “ABBA” 和“AAAA”中的一种。每句诗句的韵脚都编了号，具有相同编号的句子代表有相同的韵脚。现在，黄药师想删掉一些句子，使得剩下的都是遵循押韵规则的四行诗，而且不允许改变诗句的顺序。找出满足条件最长的诗歌
分析：贪心 观察韵脚 两个A和两个B 则sum++ 当A和B相同 也sum++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;

const int N = 5100;

int n,sum;
map<int,int>m;

int main()
{
    int s=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        m[x]++;
        if(m[x]==2)s++;
        if(s==2)//各有两个情况 A B
        {
            s=0;
            sum++;
            m.clear();
        }
        if(m[x]==4)//四个一样 A=B
        {
            s=0;
            sum++;
            m.clear();
        }
    }
    printf("%d\n",sum);

    return 0;
}