题解P6389 [COCI2007-2008#4] MUZICARI

· · 题解

题目大意：

给你 n 个人，每个人有一个休息的时长，问在每人都需休息的情况下每人开始休息的时刻。

sol:

看到其他题解有 O(n) 的做法，那我来讲一种 O(t) 的做法。

第一眼看感觉有点类似 P1223 排队接水的一道贪心题，后来仔细一看才发现根本就是个简单的模拟。

因为同一时刻可以休息两个人，那么我们定义 k1 , k2 分别表示正在休息的两个人需要多久才能休息好。同时我们不难发现第一个人与第二个人肯定在第 0 时刻开始休息。那么接下来我们只需要枚举每个时间点，然后将 k1,k2 都 -1 。若一个人休息完毕（即 k1=0 或 k2=0），则输出该时间点并让下一个人开始休息，所有人都休息完时退出即可。

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int t,n,i,j,k1,k2,kk,a[555];
int main()
{
        cin >> t >> n;
        cout << "0" << " " << "0" << " ";//前两人从第0时刻开始休息
        for (i=1; i<=n; i++) cin >> a[i];
        k1=a[1]; k2=a[2]; kk=3;//kk表示下一个休息的人的编号
        for (i=1; i<=t; i++)
        {
                k1--;
                k2--;
                if (k1==0)
                {
                        cout << i << " ";
                        k1=a[kk];
                        kk++;
                }//这个人休息好了就输出该时间点，并轮到下一个人开始休息
                if (kk>n) return 0; //所有人都休息好了就推出
                if (k2==0)
                {
                        cout << i << " ";
                        k2=a[kk];
                        kk++;
                }//同上
                if (kk>n) return 0; //同上
        }
        return 0;
}

Tips:

  1. 题目告诉我们方案数不唯一，不要因没有看清题而走弯路。