题解CF545D【Queue】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 883 | 阅读时长 ≈ 1 分钟

这道题基本思路就是贪心（标签里的队列是什么鬼不会是因为标题叫队列吧）

主要还是证明贪心的正确性(大佬勿喷)

设总等待时间为 $time$ , $n$个人等待时间分别为$t_{1}$,$t_{2}$,$t_{3}$···$t_{n}$,要使总等待人数最少,则$time$
要取最小值:

$time$ = $t_{1}$+($t_{1}$+$t_{2}$)+($t_{1}$+$t_{2}$+$t_{3}$)+···+($t_{1}$+$t_{2}$+$t_{3}$+···$t_{n}$)

$time$ = $n \cdot t_{1}$+ $(n-1)\cdot t_{2}$+ ··· + $t_{n}$

当$t_{1} \le $ $t_{2} \le$ ······ $t_{n}$ 时，$time$为最小值(简单的证明过程)

——————————————————————————————————————————

所以只要先每个人的等待时间排序一遍，设定一个总时间变量$time$,只要$time$小

于这个人的等待时间答案就+1，同时$time$也要加上这个人的等待时间

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int n,t[100010],sum,ti;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	sort(t+1,t+n+1);//排序（从小到大)
	for(int i=1;i<=n;i++)
	{
		if(t[i]>=ti)//如果time<这个人等待时间
		{
			sum++;//答案+1
			ti+=t[i];//time加上这个人的等待时间
		 } 
	}
	printf("%d",sum);
	return 0;
}