P2240 部分背包问题

最简单的贪心，策略是计算每单位重量的价值$v_i\div m_i$

AC Code

#include<bits/stdc++.h>
using namespace std;

struct jelly{
    double m,v;
}j[102];

bool cmp(jelly j1,jelly j2){
    return (j1.v/j1.m) > (j2.v/j2.m);
}

int main(){
    int n,t;
    double bag = 0.0;
    cin>>n>>t;
    for(int i = 0;i < n;i++){
      cin>>j[i].m>>j[i].v;
    }
    sort(j,j+n,cmp);
    for(int i = 0;i < n;i++){
        if(t-j[i].m >= 0){
            bag += j[i].v;
            t -= j[i].m;
        }else{
            bag += double(t)*(j[i].v/j[i].m);
            break;
        }
    }
    printf("%.2lf",bag);
    return 0;
}

P1223 排队接水

贪心的部分很简单，策略肯定是$T_i$大的放后面防止前面的人等。

#include <bits/stdc++.h>
using namespace std;

struct people{
    int t,idx;
}p[1002];

bool cmp(people a,people b){
    return a.t < b.t;
}

int main(){
    int n;
    double time = 0;
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>p[i].t;
        p[i].idx = i;
    }
    sort(p+1,p+1+n,cmp);
    for(int i = 1;i <= n;i++){
        cout<<p[i].idx<<" ";
        time += (n-i)*p[i].t;
    }
    printf("\n%.2f",time/n);
    return 0;
}

P1803 凌乱的yyy / 线段覆盖

贪心策略:右端点排序，能取就取

#include <bits/stdc++.h>
#define MAXN 1000005 
using namespace std;

struct qwq{
    int l,r;
}orz[MAXN];

bool cmp(qwq otz,qwq sto){
    return otz.r < sto.r;
}

int main(){
    int n,count = 1,endt;
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>orz[i].l>>orz[i].r;
    }
    sort(orz+1,orz+1+n,cmp);
    endt = orz[1].r;
    for(int i = 2;i <= n;i++){
        if(orz[i].l >= endt){
            count++;
            endt = orz[i].r;
        }
    }
    cout<<count;
    return 0;
}

P3817 小A的糖果

贪心策略:遍历一次，要吃就吃

#include <bits/stdc++.h>
#define MAXN 100005 
using namespace std;

long long n, x, ans;
long long caddy[MAXN];
int main()
{
    cin >> n >> x;
    for (long long i = 1; i <= n; i++)
    {
        cin >> caddy[i];
        if (caddy[i] + caddy[i - 1] > x)
        {
            ans += caddy[i] + caddy[i - 1] - x;
            caddy[i] -= caddy[i] + caddy[i - 1] - x;
        }
    }
    cout << ans;
    return 0;
}

P1106 删数问题

贪心策略: 保证每一位最优

#define MAXN 100005 
using namespace std;

int main(){
    string num;
    int l,start = 0,min,flag = 1;
    cin>>num>>l;

    while(l){
            min = start;
        for(int i = start+1;i <= start+l;i++)
            if(num[i] < num[min]) min = i;
        l -= (min - start);
        start = min+1;
        if(num[min] != '0'){
            cout<<num[min];
            flag = 0;
        }
    }
    
      while(num[start] != '\0'){
          cout<<num[start++];
          flag = 0;
      }

      if(flag) cout<<0;
    return 0;
}

P1478 陶陶摘苹果（升级版）

贪心策略:排除摘不到的，然后从用力气小的开始摘

#include<bits/stdc++.h>
using namespace std;

struct qwq{
    int x,y;
}orz[5005];

bool cmp(qwq otz,qwq sto){
    return otz.y < sto.y;
}

int main() {
    int n,s,a,b,ans = 0;
    cin>>n>>s>>a>>b;
    for (int i = 0; i < n; i++){
        cin>>orz[i].x>>orz[i].y;
        if(orz[i].x>(a+b)){
            i--;n--;
        }
    }

    sort(orz,orz+n,cmp);
    for(int i = 0;i < n;i++){
        if((s - orz[i].y) >= 0)
            ans++;
        else
             break;
        s -= orz[i].y;
    }
    cout<<ans<<endl;
    return 0;
}

P5019 铺设道路

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,d[100005] = {0},ans = 0;
    cin>>n;
    for (int i = 1; i <= n; i++){
        cin>>d[i];
        if(d[i] > d[i-1]) ans += (d[i]-d[i-1]);
    }
    cout<<ans;
    return 0;
}