| Buy tickets |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Problem description |
| There are N people who want to buy some tickets, and there are M places to serve them. These people are numbered from 1 to N , and person i will be served in Ti minites. If N > M, some people will have to wait. Now we want to rearrange the sequence of these people so that the sum of the waiting time of all the people will be minimized, and your task is to calculate the minimum waiting time. |
| Input |
| The first line is two integers N(1 <= N <= 1000) and M(1 <= M <= 100), which is the number of the people and the number of places to serve them. The following n lines is the time which the N people need to be served. |
| Output |
| Only one integer, the minimum waiting time. |
| Sample Input |
5 3 3 4 2 8 4 |
| Sample Output |
5 |
//// 第一行输入 n m ,n 表示需要买票的总人数，m 表示提供服务的窗口数目，接下来的 n 行每行一个整数表示第 i （1<=i<=n) 个人需要的服务时间，计算所有人总共的等待时间,思路“先给需要服务时间少的人提供服务”。。／／／水题 ，仅为充数 。。。
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int wait[1002],n,m;
cin>>n>>m;
for(int i=0; i<n; i++)
cin>>wait[i];
if(m>=n)
cout<<0<<endl;
else{
sort(&wait[0],&wait[n]);
int times=0,i=m;
do{
times += wait[0]*(n-i);
for(int j=0,t=wait[0]; j<m && i<n; j++){
wait[j]=wait[j]-t;
if(wait[j]==0)
wait[j]=wait[i++];
}
sort(&wait[0],&wait[m]);
}while(i<n);
cout<<times<<endl;
}
return 0;
}
评论