首页 > 代码库 > XJOIWinterCampPrecontest1-P2队列

XJOIWinterCampPrecontest1-P2队列

2024-09-02 17:37:43   219人阅读

2 排队
2.1 题目
有n 个人打水，第i 个人打水需要ai 的时间。有K 个水龙头，你可以随意安排他们打水
的顺序以及使用哪一个水龙头，但是每一时刻每一个水龙头只能有一个人使用且一个人一旦开
始打水就不能终止。
问最少的总等待时间，对每一个K 2 [1; n] 输出。
2.2 输入格式
第一行输入一个整数n 。
第二行输入n 个整数表示ai。
2.3 输出格式
输出一行n 个空格隔开的整数表示答案。
2.4 输入样例
5 1 2 3 4 5

2.5 输出样例
35 22 18 16 15
2.6 数据范围
对于20% 的数据，n  103。
对于50% 的数据，n  104。
对于100% 的数据，n  105，1  ai  108。

这次比赛最水的题。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 long long d[100001];
 6 int main()
 7 {
 8     int n;
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++) scanf("%lld",&d[i]);
11     sort(d+1,d+n+1);
12     for(int i=2;i<=n;i++) d[i]+=d[i-1];
13     long long ans=0;
14     for(int i=1;i<=n;i++)
15     {
16         ans=0;
17         for(int j=n;j>0;j-=i) ans+=d[j];
18         printf("%lld ",ans);
19     }
20     return 0;
21 }

 

XJOIWinterCampPrecontest1-P2队列


联系
我们