关于本题贪心的一些问题
查看原帖
关于本题贪心的一些问题
598700
vanderboom楼主2024/9/23 19:07

如果我读题没错的话,

本题核心就是将若干数分两组,使两组数的差的绝对值最小

所以很自然想到贪心

我们声明一个v表示差值,将数据排序从大到小考虑,若v不大于0,则v加上该数,否则v减去该数

最后将v取绝对值,总时间减v再除以二,最后加v 即为该科最短时间

然而交上去全wa。。并且没数据。。。。

思路有问题的话望指正,谢谢辣

有hack也行

代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int s[4],t[200];
int cmp(int a,int b){return b<a;}
int cal(int n){
	int i=0,v=0,cnt=0;
	while(i<n){
		cnt+=t[i];
		if(v<=0)v+=t[i];
		else v-=t[i];
		i++;
	}
	v=abs(v);
	return (cnt-v)/2+v;
}
int ans;
int main(){
	for(int i=0;i<4;i++){cin>>s[i];}
	for(int i=0;i<4;i++){
		for(int j=0;j<s[i];j++){
			cin>>t[j];
		}
		sort(t,t+s[i],cmp);
		ans+=cal(s[i]);
	}
	cout<<ans;
	return 0;
}
2024/9/23 19:07
加载中...