洛谷 2392 考前临时抱佛脚 求纠错

Question

题目给的测试点过了，但是提交后有问题，十个测试点都是WC

#include<bits/stdc++.h>
using namespace std;

bool cmp(int x,int y){
return x>y;
}
int main(){
int s[5];
int sum=0;
for(int i=1;i<=4;i++)
cin>>s[i];
for(int i=1;i<=4;i++){ //当复习第i科时
int a[s[i]+5];
for(int j=1;j<=s[i];j++)
cin>>a[j]; //输入s道题目需要的时间
sort(a,a+s[i],cmp); //对s道题目按升序排序，降序也可以
int l=0;
int r=0;
for(int j=1;j<=s[i];j++){
if(j/2) l+=a[j]; //如果是第奇数个题，放到左脑
if(j/2==0) r+=a[j]; //如果是第偶数个题，放到右脑
//if(l<=r) l+=a[j];
//else r+=a[j];
}
sum+=max(l,r);
}
cout<<sum;
}

Answer 1

并不是说简单的排个序, 然后交替分配给左右脑就完事的. 你要让每次左右脑处理的时长的差尽可能小.
举个例子, 假设排完序后时间分别是1, 10, 11, 100. 你一上来1给左脑, 10给右脑, 11给左脑, 100给右脑, 花的时间就是110, 但是如果把1和100给左脑, 10和11给右脑, 花的时间就是101.
所里每碰到新的题需要耗费s, 假设此时左脑总共还有l, 右脑有r, 如果l<r, 那么就分配给左脑, 反之右脑.