526互联

贪心国王游戏

发布时间 2024-01-09 21:18:51作者: TomLove

贪心 耍杂技的牛

  • 国王游戏同款思路
  • 大部分贪心用的都是已经被证明过的知名的数学模型

image-20240109205302562

image-20240109205139870

  • 贪心得到的答案 >= 最优解
  • 贪心得到答案 <= 最优解

image-20240109205947410

#include<iostream>
#include<algorithm>

using namespace std;

// 给 pair<int, int>  起个别名 PII
typedef pair<int, int> PII;

const int N = 50010;

int n;
PII cow[N];

int main(){
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++){
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, w};
    }
    
    // 默认是根据  first 进行排序
    sort(cow, cow + n);
    
    /*
        二元组 pair
        cow.first 可以调用 第一个元素
        cow.second 可以调用第二个元素
        默认情况下排序时根据第一个元素进行排序
    */
    int res = - 2e9, sum = 0;
    for(int i = 0; i < n; i++){
        int w = cow[i].second, s = cow[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    
    printf("%d\n", res);
    
    return 0;
}