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

很明显的贪心。

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

但是，这种方法有一个漏洞，就是两个最大差值的数的编号完全有可能相等。于是我们考虑如果相等时，就将一个换为第二大的数，至于怎么换呢，如果

C-A

的第二大值和

B-A

的最大值之和比

B-A

的第二大值和

C-A

的最大值大，那么答案就是

A

之和加上前者，否则是

A

之和加上后者。

代码很显而易见了。

CPP

#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;
}

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

文章操作

相关推荐

评论

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