题解 P6389 【[COCI2007-2008#4] MUZICARI】

· · 题解

大家都知道，这题作为T4还是未免有的太水了一点。

基本思路大概是这样的：

  1. 一开始，第一个曲师要休息 a_1 分钟，直接让他从 0 分钟开始休息；
  2. 第二名曲师过来了，他要休息 a_2 分钟，也直接让他从 0 分钟开始休息。
  3. 第三名曲师过来了，他要休息 a_3 分钟，看是第一个曲师在的房间所休息过的人的时间总和小还是第二个曲师在的房间所休息过的人的时间总和小，哪个小选哪个，同时把自己所要休息的时间加到该房间去。

如此循环往复，得到的便是可行解，由于得到的一定在 t 分钟里面，所以 t 是无用变量。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,s1,s2,a;      //s1，s2分别代表第一和第二个房间
int main(){
    scanf("%d",&n);scanf("%d",&n);
    while(n--){
        scanf("%d",&a);
        printf("%d ",min(s1,s2));
        if(s1<s2)s1+=a;
        else s2+=a;
    }
}