描述 Description   

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

一旦任务i由某台机器完成，中途不能更换机器。

编程任务：

对任意给定的整数n 和k，以及完成任务i 需要的时间为ti，i=1~n 。编程计算完成这n个任务的最佳调度

 

 

输入格式 Input Format

        第一行有2 个正整数n 和k。

第2 行的n 个正整数是完成n 个任务需要的时间。

 

输出格式 Output Format      

        完成全部任务的最早时间。

 

样例输入 Sample Input

7 3

2 14 4 16 6 5 3

 

样例输出 Sample Output      

17

 

这道题我最开始写的时候可以说是zz了，怎么说，最开始连题都没读懂，甚至看不出这是道回溯题（我真是太弱啦！！），当时感觉和接水问题差不多（好像确实差不多？不是我的锅），在lyz大佬的指点下，才算是大概有些头绪。然后敲了没几行又卡了，最后不得已搜了两篇题解，算是彻底明白这题怎么写了。

换一个角度思考一下，一个k个可并行的机器，实际就相当于把这k个机器当做容器，将时间填入容器中去，按照时间来搜索，然后一层一层搜索，每次传的是容器中时间的最大值(在这个时间内我们可以不断地用其他机器完成别的工作，而当累加时间大于最大时间是，我们就不得已扩充容器了)

//剪枝可以使这个程序快到飞起，否则就等着tle吧….

代码如下：

1 #include 
      
        2 using namespace std; 3 int n,k; 4 int a[100086],s[100086]; 5 int minn=1000000; 6 bool ltt(int x,int y){ 7 return x>y;} 8 inline void dfs(int b,int c){ 9     if(c>=minn) return;//剪枝1号10     if(b>n){11         if(c
       
        >n>>k;26     memset(s,0,sizeof(s));27     for(int i=1;i<=n;i++)28         cin>>a[i];29     sort(a+1,a+n+1,ltt);//从大到小排序可以更快接近最优解30     dfs(1,0);31     cout<
        
         <