概念简介

贪心原理

贪心算法的核心就是一个字：贪。总是做出当前看来最优的选择，因此可知，贪心算法不从整体去考虑，它做出的选择也是局部最优选择，从而达到全局优化选择。我们只关注目前的利益，从而达到利益最大化，尽管贪心算法不一定能得到最优解，面对相当数量的一部分问题，我们是可以得到正确的答案的。

从问题的某一个初始解，一步步推论，保证每一步都是最为优化的，出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当接下来的任意一步都无法达到最优时，贪心算法结束。

贪心算法的弊病

不能保证求得的最后解是最佳的；
不能用来求最大或最小解问题；
只能求满足某些约束条件的可行解的范围。

部分背包问题

P2240 【深基12.例1】部分背包问题 - 洛谷

题意

有 N 堆金币，每堆金币有总重量 mi和总价值 vi。
背包最大承重为 T。
金币可以按任意比例分割，分割后单位价值（价值/重量）不变。
目标：在不超过背包容量的情况下，拿走最大总价值的金币。

思路

一道简单的不能再简单的入门贪心题目，为了收益最大化，肯定要选择单价最高的金币优先拿。v/m即可然后排序即可。要注意的是要用double。从贵的往便宜的拿，如果拿得下全拿，拿不下的话，填满剩余背包容量

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl "\n"
const int N=10005,inf=2e18,mod=998244353;
struct coins{
    double m, v;
    double price;
};
bool cmp(coins a, coins b){
    return a.price > b.price;
}
void solve(){
    vector<coins> coin(N);
    double n, t;
    cin >> n >> t;
    for(int i = 1; i <= n; i++){
        cin>>coin[i].m>>coin[i].v;
        coin[i].price = coin[i].v / coin[i].m;
    }
    sort(coin.begin()+1, coin.begin()+n+1, cmp);
    double sum_m= 0, sum_v = 0;
    for(int i = 1; i <= n; i++){
        if(sum_m+coin[i].m <= t){
            sum_m += coin[i].m;
            sum_v += coin[i].v;
        }
        else{
            double cha=t-sum_m;
            sum_v += cha*(coin[i].v/coin[i].m);
            break;
        }
    }
    cout << fixed << setprecision(2) << sum_v << endl;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

均分纸牌

[P1031 NOIP 2002 提高组] 均分纸牌 - 洛谷

题意

有 N 堆纸牌，每堆有若干张，纸牌总数是 N 的倍数（保证可以均分）。
移动规则：第 1 堆：只能向右移动（移到第 2 堆）第 N 堆：只能向左移动（移到第 N-1 堆）其他堆：可以向左右两边移动
一次移动：从一堆取若干张牌移到相邻堆
目标：让每堆牌数相同，求最少移动次数

思路

这其实是一个线性传输问题，在运筹学中可以证明，单向调整（从左到右）得到的流量方案 xi是使得非零流量次数最少的方法。

不说严谨的证明了，自己脑补一下。

贪心思路如下：

计算平均值 avg = 总牌数 / N
从左到右遍历：如果当前堆牌数 ≠ avg，则计算差值，需要从当前堆向下一堆移动（正数表示多出的要移走，负数表示缺少的要拿来）只要差值不为 0，就计为一次移动

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl "\n"
const int N=2e5+7,inf=2e18,mod=998244353;
int a[N];
int sum = 0,max1=0,pos=0;
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        if(a[i]>max1){
            max1=a[i];
            pos=i;
        }
    }
    int aver=sum/n;
    int cnt = 0;
    for (int i = 1; i <= n;i++){
        if(a[i]==aver){
            continue;
        }
        a[i + 1] += (a[i] - aver);
        a[i] = aver;
        cnt++;
}
    cout<<cnt<<endl;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

守序者的尊严

P5639 【CSGRound2】守序者的尊严 - 洛谷

题意

一条直线上有 n 个监控，小 Z 要从第 1 个监控位置走到第 n 个监控之后（外卖点）。
监控开关规律：第 0 秒为初始状态，之后每秒交替（开 1 秒 → 关 1 秒 → 开 1 秒 …）。
小 Z 移动规则：在监控关闭的秒数内，可以一次行动通过任意多个连续关闭的监控，耗时 1 秒。如果监控开启，则不能通过（必须等待它关闭）。
保证第 1 个监控在第 0 秒是关闭的（起步没问题）。
目标：求最少需要的总时间（秒数）。

思路

可以无脑暴力模拟锻炼一下码力，然后喜提70分

while(1){
       for (int i = pos; i <= n;i++){
           if(a[i]==0){
               pos = i;
           }
           else{
               cnt++;
               break;
           }
       }
       for(int i=pos+1;i<=n;i++){
           a[i]=1-a[i];
       }
       if(pos==n){
           break;
       }
   }

显然是不能暴力的，但是其实也不需要暴力，因为每一次其实小Z都会疾速移动到10交界处，你算一下有几个交界处就好。最后的答案是交界处个数加一。注意，如果开头是1，那么第一秒是不可以动的，要原地等一秒。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl "\n"
const int N=1000005,inf=2e18,mod=998244353;
int a[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if(a[i]!=a[i+1]){
            cnt++;
        }
    }
    if(a[1]==1){
        cnt++;
    }
    cout<<(cnt+1)<<endl;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

骑士的工作

P2695 骑士的工作 - 洛谷

题意

村庄里来了一只恶龙，他有 n 个头，每个头大小不同。恶龙到处杀人放火。骑士团里面有 m 位成员

每个人都可以砍掉至多一个大小不超过 zi 的头，需要 zi 个金币，求最小花费。

思路

有道是杀鸡焉用牛刀，所以我们肯定不能用很厉害的骑士去砍瓜切菜。而是用最菜的但是能赢的骑士去砍头。

也就是说，用能力值刚好大于等于头的大小的最便宜骑士去砍。只需要递增排列逐个遍历，从最弱到最强，看能不能砍下来。能砍下来就标记一下当前骑士已经出战过了（出战过的不能再战），然后把金币加到sum里面，break掉，到下一个头。当然砍过的头我们令其为0，如果最后有头不是0就说明头每砍完。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl "\n"
const int N=100005,inf=2e18,mod=998244353;
int head[N], kill1[N];
bool vis[N];
bool flag = true;
void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >>head[i];
    }
    for(int i = 1; i <= m; i++){
        cin >> kill1[i];
    }
    sort(kill1 + 1, kill1 + m + 1);
    sort(head + 1, head + n + 1);
    int sum = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(!vis[j]){
            if(head[i]<=kill1[j]){
                sum+=kill1[j];
                head[i] = 0;
                vis[j] = true;
                break;
            }
            }
        }
    }
    for(int i = 1; i <= n; i++){
       if(head[i]!=0){
           flag = false;
       }
    }
    if(flag){
        cout << sum << endl;
    }
    else{
        cout << "you died!"<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}