t0ur1st

题目描述：

假设有n个任务由n个可并行工作的机器来完成，完成任务i需要的时间为。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。计算完成这n个任务的最佳调度。

输入描述：

第1行由2个正整数n和k，第2行的n个正整数是完成n个任务需要的时间。

输出描述：

将计算的完成全部任务的最早时间输出。

输入样例：

7 3
2 14 4 16 6 5 3

输出样例：

17

解题思路：

水题啊，先对n个任务所需的时间进行降序排列。设第i台机器完成所有任务时所需要的时间为time[i]，对于每个任务选择当前耗时最短的那台机器来进行工作，最后取所有机器的最久工作时长来作为完成任务的最早时间。

代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,k;    //n个任务,k个可以并行工作的机器
    cin >> n >> k;
    int a[n+1];    //完成n个任务所需要的时间
    Up(i,1,n)
    {
        cin >> a[i];
    }
    sort(a+1,a+n+1,greater<int>());   //降序排列
    int time[k+1];   //第i台机器所需要的时间time[i]
    ms(time,0);
    Up(i,1,n)
    {
        int mint = INF,index = 0;   //当前耗时最短的时间mint,选择第index台机器工作
        Up(j,1,k)
        {
            if(time[j] < mint)
            {
                mint = time[j];
                index = j;
            }
        }
        time[index] += a[i];
    }
    int ans = -INF;   //完成任务的最早时间
    Up(i,1,k)
    {
        ans = max(ans,time[i]);
    }
    cout << ans << endl;
    return 0;
}