题解：P14276 [ROI 2014 Day2] 电影学院

zhujianheng · 2025-10-21 20:13:10 · 题解

很明显的贪心。

注意到最优秀的两个一定是换出来的比原先的要大很多的，于是我们考虑分别把差值先计算并放入两个数组中，再从大到小排序，最后求出最大值之和即可。

但是，这种方法有一个漏洞，就是两个最大差值的数的编号完全有可能相等。于是我们考虑如果相等时，就将一个换为第二大的数，至于怎么换呢，如果 C-A 的第二大值和 B-A 的最大值之和比 B-A 的第二大值和 C-A 的最大值大，那么答案就是 A 之和加上前者，否则是 A 之和加上后者。

代码很显而易见了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100009;
int a[N],b[N],c[N];
struct Node{
    int diff,id;
}x[N],y[N];
bool cmp(Node x,Node y){
    return x.diff>y.diff;
}
signed main(){
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i],sum+=a[i];
    for(int i=1;i<=n;i++) x[i].diff=b[i]-a[i],y[i].diff=c[i]-a[i],x[i].id=y[i].id=i;
    sort(x+1,x+1+n,cmp);
    sort(y+1,y+1+n,cmp);
    if(x[1].id==y[1].id){
        if(x[2].diff+y[1].diff>x[1].diff+y[2].diff) cout<<sum+x[2].diff+y[1].diff<<endl<<x[2].id<<" "<<y[1].id<<endl;
        else cout<<sum+x[1].diff+y[2].diff<<endl<<x[1].id<<" "<<y[2].id<<endl;
        return 0;
    }
    cout<<sum+x[1].diff+y[1].diff<<endl<<x[1].id<<" "<<y[1].id<<endl;
    return 0;
}