AcWing125. 耍杂技的牛(贪心+推公式)

2023-12-23 20:53:06

题目链接AcWing125. 耍杂技的牛
在这里插入图片描述

分析:
这是一道贪心问题,我们假设牛最终的摆放顺序(从上大小)为1,2,3,...i,i+1,...,n,当存在相邻的两头牛i,i+1如果 w i + s i > w i + 1 + s j + 1 w_i+s_i> w_{i+1}+s_{j+1} wi?+si?>wi+1?+sj+1? 那么交换两头牛i,i+1的位置,后所有牛风险值的最大值不会变大。
证明:
首先,可以容易想到交换两头牛i,i+1的位置不会对1~i-1i+1~n牛的风险值产生影响
我们将1~i-1头牛的重量表示为 w 上 w_{上} w?
那么,
i头牛的风险值为 w 上 ? s i w_{上}-s_i w??si?
i+1头牛的风险值为 w 上 + w i ? s i + 1 w_{上}+w_i-s_{i+1} w?+wi??si+1?
此时,两头牛i,i+1的最大风险值为 max ? ( w 上 ? s i , w 上 + w i ? s i + 1 ) \max(w_{上}-s_i,w_{上}+w_i-s_{i+1}) max(w??si?,w?+wi??si+1?)
交换两头牛i,i+1的位置后
i头牛的风险值为 w 上 ? s i + 1 w_{上}-s_{i+1} w??si+1?
i+1头牛的风险值为 w 上 + w i + 1 ? s i w_{上}+w_{i+1}-s_{i} w?+wi+1??si?
此时,两头牛i,i+1的最大风险值为 max ? ( w 上 ? s i + 1 , w 上 + w i + 1 ? s i ) \max(w_{上}-s_{i+1},w_{上}+w_{i+1}-s_{i}) max(w??si+1?,w?+wi+1??si?)
因为 w i + s i ≥ w i + 1 + s j + 1 w_i+s_i\geq w_{i+1}+s_{j+1} wi?+si?wi+1?+sj+1? ,所以有 w i ? s i + 1 ≥ w i + 1 ? s j i w_i-s_{i+1}\geq w_{i+1}-s_{ji} wi??si+1?wi+1??sji?
所以有:
w 上 + w i ? s i + 1 > w 上 + w i + 1 ? s i w_{上}+w_i-s_{i+1}>w_{上}+w_{i+1}-s_{i} w?+wi??si+1?>w?+wi+1??si?
w 上 + w i + 1 ? s i > w 上 ? s i w_{上}+w_{i+1}-s_{i}>w_{上}-s_i w?+wi+1??si?>w??si?
w 上 + w i ? s i + 1 > w 上 ? s i + 1 w_{上}+w_i-s_{i+1}>w_{上}-s_{i+1} w?+wi??si+1?>w??si+1?
所以有 max ? ( w 上 ? s i , w 上 + w i ? s i + 1 ) > max ? ( w 上 ? s i + 1 , w 上 + w i + 1 ? s i ) \max(w_{上}-s_i,w_{上}+w_i-s_{i+1})>\max(w_{上}-s_{i+1},w_{上}+w_{i+1}-s_{i}) max(w??si?,w?+wi??si+1?)>max(w??si+1?,w?+wi+1??si?)
所以,存在相邻的两头牛i,i+1如果 w i + s i > w i + 1 + s j + 1 w_i+s_i> w_{i+1}+s_{j+1} wi?+si?>wi+1?+sj+1? 那么交换两头牛i,i+1的位置,后所有牛风险值的最大值会变小。
类似于冒泡排序的思路,可以用贪心的思想来找到该问题的一个最优解,就是按照 w i + s i w_i+s_i wi?+si?从小到大的顺序从高往低摆放牛

代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=5e4+10;
typedef pair<int,int> pii;
typedef long long ll;
vector<pii> v;

int main(){
    int n;
    int res=-1e9;
    cin>>n;
    for(int i=0;i<n;i++){
        int w,s;
        scanf("%d%d",&w,&s);
        v.push_back({w+s,w});
    }
    sort(v.begin(),v.end());
    ll ans=0;
    for(int i=0;i<v.size();i++){
        if(ans-v[i].first+v[i].second>res) res=ans-v[i].first+v[i].second;

        ans+=v[i].second;
    }
    cout<<res;
    return 0;
}

文章来源:https://blog.csdn.net/qq_43851311/article/details/135173205
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。