P1842 奶牛玩雜技

題目描述

N N N 頭奶牛中的每一頭都有自己的重量 W i W_i Wi? 以及強壯程度 S i S_i Si?，
一頭牛支撐不住的可能性取決于它頭上所有牛的總重量（不包括它自己）減去它的身體強壯程度的值，現在稱該數值為風險值，風險值越大，這只牛撐不住的可能性越高，
您的任務是確定奶牛的排序，使得所有奶牛的風險值中的最大值盡可能的小，
鏈接

思路

我們先將奶牛按照順序排列，如果有兩頭奶牛調換后結果可能更優，就調換他們，
現在有兩頭奶牛分別在從頂端數位置 i , j i,j i,j 上，滿足 i < j i<j i<j ，調換他們的條件為： m a x ( W ? s [ i ] , W ′ ? s [ j ] ) > m a x ( W ? s [ j ] , W ′ ? w [ i ] + w [ j ] ? s [ i ] ) max(W-s[i],W'-s[j])>max(W-s[j],W'-w[i]+w[j]-s[i]) max(W?s[i],W′?s[j])>max(W?s[j],W′?w[i]+w[j]?s[i])
所以……就什么也沒看出來，
當 W ? s [ i ] > W ′ ? s [ j ] , W ? s [ j ] > W ′ ? w [ i ] + w [ j ] ? s [ i ] W ? s [ i ] > W ? s [ j ] , s [ i ] < s [ j ] W > W ′ ? w [ i ] + w [ j ] w [ j ] < 0 , 舍 當 W ? s [ i ] > W ′ ? s [ j ] , W ? s [ j ] ≤ W ′ ? w [ i ] + w [ j ] ? s [ i ] W ? s [ i ] > W ′ ? w [ i ] + w [ j ] ? s [ i ] , w [ j ] < 0 , 舍 當 W ? s [ i ] ≤ W ′ ? s [ j ] , W ? s [ j ] > W ′ ? w [ i ] + w [ j ] ? s [ i ] ? s [ j ] > ? w [ i ] + w [ j ] ? s [ i ] , w [ i ] + s [ i ] > w [ j ] + s [ j ] 當 W ? s [ i ] ≤ W ′ ? s [ j ] , W ? s [ j ] ≤ W ′ ? w [ i ] + w [ j ] ? s [ i ] W ′ ? s [ j ] > W ′ ? w [ i ] + w [ j ] ? s [ i ] , w [ i ] + s [ i ] > w [ j ] + s [ j ] 當W-s[i]>W'-s[j],W-s[j]>W'-w[i]+w[j]-s[i]\\ W-s[i]>W-s[j],s[i]<s[j]\\ W>W'-w[i]+w[j]\\ w[j]<0,舍\\ 當W-s[i]>W'-s[j],W-s[j]\le W'-w[i]+w[j]-s[i]\\ W-s[i]>W'-w[i]+w[j]-s[i],w[j]<0,舍\\ 當W-s[i]\le W'-s[j],W-s[j]>W'-w[i]+w[j]-s[i]\\ -s[j]>-w[i]+w[j]-s[i],w[i]+s[i]>w[j]+s[j]\\ 當W-s[i]\le W'-s[j],W-s[j]\le W'-w[i]+w[j]-s[i]\\ W'-s[j]>W'-w[i]+w[j]-s[i],w[i]+s[i]>w[j]+s[j]\\ 當W?s[i]>W′?s[j],W?s[j]>W′?w[i]+w[j]?s[i]W?s[i]>W?s[j],s[i]<s[j]W>W′?w[i]+w[j]w[j]<0,舍當W?s[i]>W′?s[j],W?s[j]≤W′?w[i]+w[j]?s[i]W?s[i]>W′?w[i]+w[j]?s[i],w[j]<0,舍當W?s[i]≤W′?s[j],W?s[j]>W′?w[i]+w[j]?s[i]?s[j]>?w[i]+w[j]?s[i],w[i]+s[i]>w[j]+s[j]當W?s[i]≤W′?s[j],W?s[j]≤W′?w[i]+w[j]?s[i]W′?s[j]>W′?w[i]+w[j]?s[i],w[i]+s[i]>w[j]+s[j]
那如果我只知道 i < j , w [ i ] + s [ i ] > w [ j ] + s [ j ] i<j,w[i]+s[i]>w[j]+s[j] i<j,w[i]+s[i]>w[j]+s[j] ，能不能推出來他需要調換呢？
若 W ? s [ j ] > W ′ ? w [ i ] + w [ j ] ? s [ i ] , W ′ > W , ∴ W ′ ? s [ j ] > W ? s [ j ] 若 W ? s [ j ] ≤ W ′ ? w [ i ] + w [ j ] ? s [ i ] , ? s [ j ] > ? w [ i ] + w [ j ] ? s [ i ] , W ′ ? s [ j ] > W ′ ? w [ i ] + w [ j ] ? s [ i ] 若W-s[j]>W'-w[i]+w[j]-s[i],W'>W,\therefore W'-s[j]>W-s[j]\\ 若W-s[j]\le W'-w[i]+w[j]-s[i],-s[j]>-w[i]+w[j]-s[i],W'-s[j]>W'-w[i]+w[j]-s[i] 若W?s[j]>W′?w[i]+w[j]?s[i],W′>W,∴W′?s[j]>W?s[j]若W?s[j]≤W′?w[i]+w[j]?s[i],?s[j]>?w[i]+w[j]?s[i],W′?s[j]>W′?w[i]+w[j]?s[i]
所以我只需要按 w [ i ] + s [ i ] w[i]+s[i] w[i]+s[i] 排序即可

這真是十分的 Amazing 啊！
——畢導

Code

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

struct node
{
    int val,w;
    friend bool operator < (node _,node __){return _.val<__.val;}
}a[50005];

int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int w,s;
        scanf("%d%d",&w,&s);
        a[i].val=w+s;
        a[i].w=w;
    }
    sort(a+1,a+n+1);
    int ans=-1e9;
    for(int i=1,sum=0;i<=n;i++)
    {
        int w=a[i].w,s=a[i].val-w;
        ans=max(ans,sum-s);
        sum+=w;
    }
    cout<<ans<<endl;
    return 0;
}