目录

贪心真的太玄学了

1.入门级

学生分组
有N组学生，给出初始时每组中的学生个数，再给出每组学生人数的上界RRR和下界L(L≤R)L(L \le R)L(L≤R)，每次你可以在某组中选出一个学生把他安排到另外一组中，问最少要多少次才可以使NNN组学生的人数都在[L,R]中。
思路：
需要考虑-1和非-1的情况；
非-1即可以分配，那么大于上限的要调走，调到小于上限的组里，最少次数为需要调动的最大值。
-1即无法达到要求，则人数过多或过少；

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n,m,l,r,a[maxn],sum,in,out;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    cin>>l>>r;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>r)out+=a[i]-r;
        if(a[i]<l)in+=l-a[i];
    }
    if(sum>n*r||sum<n*l)cout<<-1<<endl;
    else cout<<max(out,in)<<endl;
    return 0;
}

2.区间覆盖升级版（多重区间覆盖）

喜欢（陪别人）吃饭的燕队
题目描述
众所周知，燕队有很多事情需要处理，其中最重要的就是陪他的暧昧对象吃饭，考虑到他强大的交际能力，他每个时刻可以同时最多和k个人吃饭，现在给出n个暧昧对象及他们需要安排吃饭的开始时间s和结束时间t（[s, t]），求出燕队最多能和多少个暧昧对象吃饭

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3;
int t,n,m,k,now[maxn],ans;
struct node
{
    int l,r;
}a[maxn];
bool cmp(node a,node b)
{
    return a.r<b.r;//按结束时间早的排
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        ans=0;
        memset(now,0,sizeof(now));
        for(int i=1;i<=n;i++)
            cin>>a[i].l>>a[i].r;
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
            int minn=23333333;
            int nx=0;
            for(int j=1;j<=k;j++)//同时数组now中能装K个人
            {//a[i].l-now[j]<minn指是在这个时间区间内
                if(a[i].l>now[j]&&a[i].l-now[j]<minn)//每次比较都是跟上一个时间区间比较，每一个时间区间只能同时存在K个人，满了以后之后的都跟上一个时间区间比较
                {
                    nx=j;
                    minn=a[i].l-now[j];//求得现在的时间区间
                }
            }
            if(nx!=0)//符合条件（上一个结束吃下一个人）就ans++
            {
                now[nx]=a[i].r;
                ans++;
            }
        }
        cout<<ans<<endl;
    }
}

3.CF1066B Heaters

题意描述：
Vova先生的家可以看作一个n×1的矩形，寒冷的冬天来了，
Vova先生想让他的家里变得暖和起来。现在我们给你Vova先生家的平面图，其中
1表示这个地方是加热炉，0表示这个地方什么也没有。所有加热器都有一个加热半径r,一个位于ai加热器可以加热[ai​−r+1,ai​+r−1]的范围。现在，Vova先生想让他的整个家都变得暖和，一开始所有的加热器都是关闭的，请你求出Vova先生最少要开几个加热器才能使整个家变得暖和
输入格式：
第一行:两个整数n,r(1≤n,r≤1000),含义如上第二行，n个整数，表示Vova家的地图
**输出格式：**一个整数，表示Vova先生至少要打开几个加热器
输入输出样例
输入

6 2
0 1 1 0 0 1

输出

3

题意：有一堆加热器，加热器的加热范围是r求最少打开几个可以加热整个范围
思路：这很显然是一道贪心，既然我们要保证最少，那么我们就需要放的加热器个数是最优的。简单来说，我们找到第一个加热器后，最优的方法就是在这个加热器位置的右边2*r-1处再放一个加热器，这时候每个位置都只有一个加热器在加热这就满足了最优的条件那么如果这个位置没有加热器呢？那只有退一步走，找到这个最优位置左边的第一个加热器就是当前最优的位置
如果找不到，那么就不可能成功，输出-1

#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"OK"<<endl
#define firststep ios::sync_with_stdio(false),cout.tie(0),cin.tie(0)
typedef long long ll;
const ll maxn=1e5+10;
ll n,r,a[maxn],ans;
bool flag[maxn];
int main()
{
    firststep;
    cin>>n>>r;
    for(ll i=1;i<=n;i++)
        cin>>a[i];
    for(ll i=r;;)
    {
        if(a[i])
        {
            ans++;
            flag[i]=1;
            if(i+r-1>=n)
                break;
            i=i+2*r-1;
            continue;
        }
        while(!a[i]&&i&&!flag[i])i--;//如果没有就往左找，（！flag）的作用是让他停下来，方便下面一行直接输出-1return;
        if(flag[i]||i==0){puts("-1");return 0;}//找不到或者没有就输出-1return;
        ans++;flag[i]=1;
        if(i+r-1>=n)break;
        i=i+2*r-1;
    }
    cout<<ans<<endl;
    return 0;
}

4.拿东西(贪心+博弈)


题上说要尽可能的使自己的分比别人的高，最大化自己和对方的差值，也就是说把别人得分高的那个抢走，让自己涨分多，到对面回合涨分少，🙃走别人的路,让别人无路可走这就是博弈的秘诀

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+7;
const ll mod=1e9+7;
ll n,ansa[N],ansb[N],x;
bool val[N];
struct node
{
    ll vis,idx;
}a[N];
bool cmp(node x,node y)
{
    return x.vis>y.vis;
}
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].vis,a[i].idx=i;
    for(int i=1;i<=n;i++)
        cin>>x,a[i].vis+=x;// 选总分最高的然后排序,每个人都优先抢分最高的那一个
    sort(a+1,a+1+n,cmp);
    ll cnt1=0,cnt2=0;
    ll i=1;
    bool flag=1;
    while(cnt1+cnt2<n)
    {
        if(flag)
        {
            while(val[a[i].idx])i++;
            ansa[++cnt1]=a[i].idx;
            val[a[i].idx]=1;
            flag=0;
        }
        else
        {
            while(val[a[i].idx])i++;
            ansb[++cnt2]=a[i].idx;
            val[a[i].idx]=1;
            flag=1;
        }
    }
    for(int i=1;i<=cnt1;i++)
    {
        if(i!=cnt1)
        cout<<ansa[i]<<" ";
        else cout<<ansa[i];
    }
    cout<<endl;
    for(int i=1;i<=cnt2;i++)
    {
        if(i!=cnt1)
        cout<<ansb[i]<<" ";
        else cout<<ansb[i];
    }
    cout<<endl;
    return 0;
}

P1209 [USACO1.3]修理牛棚 Barn Repair(贪心+逆向思维)

题目+答案

进阶

1.P2870 [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold（加强版)(贪心+hash哈希）


详解

2.[SCOI2005]栅栏（贪心+二分+dfs）

题目描述
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。
你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。
输入格式
第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长度。
接下来一行(即第m+2行)为整数n(n <= 1000)，表示约翰需要多少木材。
接下来n行表示他所需要的每一块木板的长度。木材的规格小于32767。（对于店老板提供的和约翰需要的每块木板，你只能使用一次）。
输出格式
只有一行，为约翰最多能够得到的符合条件的木板的个数。
这是一个答案