P10205 [JOI 2024 Final] 室温 / Room Temperature

题目描述

K 董事长负责调节高管们的房间的室温，他希望高管们能尽可能舒适地工作。

现在房间里有 $N$ 位高管。每位高管都有一个从 $1$ 到 $N$ 的编号。不穿外套时，高管 $i(1\le i\le N)$ 的舒适温度是 $A_i$ 度。另外，每位高管每穿一件外套，舒适温度就会降低 $T$ 度。也就是说，高管 $i$ 如果穿了 $k$ 件外套，那么高管 $i$ 的舒适温度就是 $A_i-kT$ 度。

如果房间的温度是 $x$ 度，某位高管的舒适温度是 $y$ 度，那么这位高管的不舒适度就是 $|x-y|$。其中，$|t|$ 表示 $t$ 的绝对值。每位高管会根据房间的温度，穿上大于等于 $0$ 件合适的外套，使得不舒适度最小。

K 董事长把高管们的不舒适度的最大值称为房间的不舒适度，并决定要把房间的温度设定为使得房间的不舒适度最小的值。但是，设定的温度必须是整数。

给定高管和舒适温度的信息。编写一个程序，求出房间的不舒适度可能的最小值。

输入格式

第一行包含两个整数 $N,T$。

第二行包含用空格分隔的 $N$ 个整数 $A_1,A_2,\dots ,A_N$。

输出格式

输出一行一个整数，表示房间的不舒适度可能的最小值。

输入输出样例 #1

输入 #1

2 4
19 24

输出 #1

1

输入输出样例 #2

输入 #2

3 1
21 19 23

输出 #2

0

输入输出样例 #3

输入 #3

6 8
24 22 21 25 29 17

输出 #3

2

说明/提示

对于所有输入数据，满足：

• $2\le N\le 5\times 10^5$
• $1\le T\le 10^9$
• $1\le A_i\le 10^9(1\le i\le N)$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
1	$N=2$	15
2	$N\le 3000,T=1$	5
3	$N\le 3000,T\le 2$	30
4	$N\le 3000,T\le 3000$	35
5	无附加限制	15

C++实现

#include<bits/stdc++.h>
using namespace std;
int n,a[500002],t,maxd,k;//变量名如题意
int main()
{
    scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]%=t;//边输入边取模
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		maxd=max(maxd,a[i+1]-a[i]);
	maxd=max(maxd,a[1]+t-a[n]);
	k=ceil((double(t-maxd))/2.0);
	printf("%d",k);
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容