P6243 [USACO06OPEN] The Milk Queue G

wanghx · 2023-08-22 14:25:14 · 题解

传送门

很明显这题应该排序和贪心。

知道了要贪心，就要知道贪心策略。

题目上说要求挤奶所需的最短时间，我们就需要第一道工序和第二道工序的时间要尽可能差值越小。

可以得出两头奶牛所用的时间为 a_x+ \max(a_y,b_x)+b_y。看见大佬们都化简了，本蒟蒻不会化简。

如果你只贪心，会 TLE，所以我们加上前缀和。

struct node{
    int a,b;
}a[N];
bool cmp(node x,node y){
    return x.a+y.b+max(x.b,y.a)<x.b+y.a+max(x.a,y.b);
}
int n,sum,ans;
signed main(){
    n=read();
    for(int i=1;i<=n;++i) a[i].a=read(),a[i].b=read();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;++i) sum+=a[i].a,ans=max(ans,sum)+a[i].b;前缀和
    write(ans);
    return 0;
}