寂静的角落 星空在前,路在脚下
Contest Start
发布于: 2021-06-28 更新于: 2021-06-28 分类于: 题解 阅读次数: 

这道题只有 6000 人做出来了,而 B 题有 8000 人,但其实还是很简单的。

Contest Start

提交地址:洛谷 CF1539ACodeForces CF1539A

题目大意

有 $n$ 个人比赛,每隔 $x$ 分钟有一人开始比赛,每个人比赛时长为 $t$,当每个人比赛结束时会有一个不满意程度,为已经开始比赛(或现在开始比赛)但尚未完成比赛的参与者人数,求所有人的不满意程度。

分析

盯着看一会儿,发现前几个人的不满意程度不一样,后面的人则是比前面的人少一。

我们看这组数据 4 2 5

第一、二个人的贡献为 $2$,第三个人为 $1$,第四个人没有贡献,和为 $5$。

这组 10 2 10

我们发现前几个的贡献为 $5$ ,第五到第十贡献为 $5, 4, 3, 2, 1, 0$,和为 $35$。

我们发现了规律,前几个都是 $\lfloor t \div x \rfloor$,最后一个往前为 $0$ 到 $\lfloor t \div x \rfloor$ 的每次增加一的数列,那么答案就有了。

注意开 long long,如果 $\lfloor t \div x \rfloor > n$ 的话等差数列是到不了 $\lfloor t \div x \rfloor$ 的,特判就行。

$\color{green}\text{code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
ll k, n, x, t, tmp, ans;
int main() {
cin >> k;
while (k--) {
cin >> n >> x >> t;
tmp = t / x, ans = 0;
if (n < tmp) {
ans = (1 + n - 1) * (n - 1) / 2;
cout << ans << endl;
continue;
}
ans += (1 + tmp) * tmp / 2;
n -= (1 + tmp);
cout << ans + n * tmp << endl;
}
return 0;
}
本文默认采用 署名-非商业性使用-相同方式共享 4.0 国际 许可证