首页 > 其他分享 >Rescheduling the Exam 题解

Rescheduling the Exam 题解

时间:2023-02-14 17:35:29浏览次数:39  
标签:last Exam 修改 int 题解 距离 相邻 Rescheduling 题意

题意:

题意简单明了,就不多赘述了。

解题方法:

这道题我们要考虑贪心。由于我们只有一次修改 \(a_i\) 的机会,所以我们修改的值一定是产生最小距离的两个相邻的点之中修改。

那么如何修改是最优的呢?有一下两种情况:

  1. 插入到距离最大的两个相邻点的最中间。因为只有插入到距离最大的两个相邻点的最中间,才能使它和相邻的点的距离最大。

  2. 插入到最后的 \(d\) 这个时间。

在这两种情况中取最近距离的 \(max\) 即可。

另外注意,这里求距离的公式有点另类。

代码实现:

#include <bits/stdc++.h>
using namespace std;
int t, n, d, a[200001];
int dis(int x, int y) {return a[x] - a[y] - 1;}
int f(int x)
{
	int Min = 2e9, Max = 0, last = 0; //Min表示最小值,Max表示最大值,last表示当前为止的最后一个点 
	for (int i = 1; i <= n; i ++)
	{
		if (i == x) continue; //千万注意要continue 
		Min = min(dis(i, last), Min);
		Max = max(dis(i, last), Max);
		last = i;
	}
	return min(Min, max((Max - 1) >> 1, d - a[last] - 1));
}
int main()
{
	scanf("%d", &t);
	while (t --)
	{
		int minn = 2e9, minx, ans = 0;
		scanf("%d%d", &n, &d);
		for (int i = 1; i <= n; i ++)
		{
			scanf("%d", &a[i]);
			if (dis(i, i - 1) < minn) //读入的时候顺便取min 
			{
				minn = dis(i, i - 1);
				minx = i;
			}
		}
		ans = f(minx);
		if (minx != 1) ans = max(ans, f(minx - 1)); //如果minx为1,就不能修改它前面的点了(以为它前面没有点) 
		printf("%d\n", ans);
	}
}

标签:last,Exam,修改,int,题解,距离,相邻,Rescheduling,题意
From: https://www.cnblogs.com/tongyuxin/p/17120307.html

相关文章

  • F1 Champions 题解
    题意已知\(n\)场比赛前\(m\)名的名字,每场比赛前\(10\)名各有不同的分数,求以下两种排名方法排名第一的人的名字。按照分数排序,若分数相同,第\(1\)次数多的优先,若......
  • Social Network 题解
    题意:题目翻译是有问题的,题目的真正意思其实是\(∀i∈[1,d]\),求在满足\([1,i]\)的规定的前提下恰好连\(i\)条边的无向图中度数最大联通块的大小减\(1\)。思路考虑......
  • P8827 [传智杯 #3 初赛] 森林 题解
    题意有一颗树,每个点有一个点权\(v\)。现在要对这棵树进行\(m\)次以下三种操作之一:删除一条边。修改一个点的点权。查询一个点\(u\)所在的树的点权之和。......
  • lg8365题解
    容易发现我们一定会先加后乘,使用调整法可以证明这个结论。并且可以发现除了\(a_i\)值为\(1\)的数外(假设他们的\(a\)值和为\(s\)),其他的数最多只会选\(1\)个做加法操作(设如......
  • Vue项目在ie浏览器中显示空白的兼容性问题解决
    问题:在ie浏览器中页面报错:SCRIPT5022:SecurityError小编也不知道原因是什么,小编是尝试了以下几种方式才显示出来,这里建议大家试试看。1、下载软件包:@babel/polyfill执......
  • elementUI的table表格改变数据不更新问题解决
    问题原因:在Vue实例创建时,以及data赋值时editable并未声明,因此就没有被Vue转换为响应式的属性,自然就不会触发视图的更新。解决方案:1、给data赋值前把editable属......
  • C++奥赛一本通递推题解
    title:C++奥赛一本通刷题记录(递推)date:2017-11-08tags:一本通openjudegecategories:OIC++奥赛一本通刷题记录(递推)2017.11.8Bygwj1139177410斐波那契数列​​op......
  • C++奥赛一本通排序题解
    title:C++奥赛一本通刷题记录(排序)date:2017-11-16tags:一本通openjudegecategories:OIC++奥赛一本通刷题记录(排序)2017.11.16Bygwj1139177410都是拿STL水的…别......
  • C++奥赛一本通刷题高精度题解
    title:C++奥赛一本通刷题记录(高精度)date:2017-11-15tags:一本通openjudegecategories:OIC++奥赛一本通刷题记录(高精度)2017.11.15Bygwj1139177410大整数加法​......
  • CodeVs天梯黄金Gold题解
    title:CodeVs天梯之Golddate:2017-12-28tags:天梯CodesVscategories:OICodeVs天梯之Gold2018.01.04Bygwj2330x01贪心​​均分纸牌​​#include<iostream>usingname......