百度star

朱雀 2022-03-20 12:09 359阅读 0赞

花了一个小时才写出来的第一题，结果网速慢提交不上去～～索性贴这里吧～～

平衡负载

Du熊正在负责一个大型的项目，目前有K台服务器，有N个任务需要用这K台服务器来完成，所以要把这些任务分成K个部分来完成，在同上台服务器上执行的任务必须是连续的任务，每个任务有各自需要的执行时间。  
  
  
例如N=5,K=2，每个任务需要时间分别为5,3,1,4,7分钟，那么我们可以分成(5)(3 1 4 7)两部分，这样第一台服务器所花时间就是5分钟，而第二台机器需要花15分钟，当然，所有任务完成的时间是按最迟完成的那台服务器的时间，即这样划分的话完成所有任务所需要的时间就是15分钟。而另外一种划分方法是(5 3 1)(4 7)，这种划分方案完成所有任务的时间就是11分钟，也是最优的一种划分方案。  
  
  
现在你的任务就是根据给定的N,K和每个任务要花费的时间，找出使完成所有任务时间最短的方案。  
  
  
   
  
  
输入：  
  
  
多组输入。  
  
  
第一行输入N和K（1<=K<=N<=10000）。  
  
  
第二行输入N个不大于1000的正整数，表示各个任要花费的时间。  
  
  
N=K=0表示输入结束。  
  
  
   
  
  
输出：  
  
  
每行输出一个整数，对应对于每个数据（除了N=K=0不用输出）。  
  
  
   
  
  
样例输入：  
  
  
5 1  
  
  
5 3 1 4 7  
  
  
5 2  
  
  
5 3 1 4 7  
  
  
5 3  
  
  
5 3 1 4 7  
  
  
10 3  
  
  
1 2 3 4 5 6 7 8 9 10  
  
  
0 0  
  
  
   
  
  
样例输出：  
  
  
20  
  
  
11  
  
  
8

#include <cstdio>
    #include <cstdlib>
    #include<cmath>
    int main()
    {
    	int N,K;
    	int *T = NULL, *KT = NULL;
    	long long sumt = 0;
    	double meant = 0.0;
    	int KTindex = 0;
    	int maxT;
    	
    	while(scanf("%d %d", &N, &K) == 2 && N && K)
    	{
    		T = (int*)malloc(N*sizeof(int));
    		KT = (int*)malloc(K*sizeof(int));
    		for(int i = 0; i < N; i++)
    		{
    			scanf("%d",T + i);
    		}	
    		meant = 0;
    		for(int i = 0; i < N; i++)
    		{	
    			meant += (double)T[i]/K;
    		}
    		sumt = 0;	
    		KTindex = 0;
    		for(int i = 0; i < N; i++)
    		{	
    			
    			if(abs(sumt + T[i] - meant) < abs(sumt - meant))
    			{
    				sumt += T[i];
    			}else {
    				KT[KTindex] = sumt;
    				KTindex++;
    				sumt = T[i];
    				meant = 0.0;
    				for(int j = i ; j < N; j++)
    				{	
    					meant += (double)T[j]/(K - KTindex);
    				}
    			}
    		}
    		KT[KTindex] = sumt;	
    		maxT = KT[0];
    		for(int i = 0; i < K;i++)
    		{
    			if(maxT < KT[i])
    			{
    				maxT = KT[i];
    			}	
    		}
    		printf("%d\n",maxT);		
    		free(T);
    		free(KT);
    	}
    	return 0;
    }