B4274 数字游戏

1. 思路分析

题目大意：

进行若干次操作，第一次将

1

个最大值变为次大值，第二次将

1

个最小值变为次小值，直到不同的数少于

3

个时，输出操作次数、剩下最大值和剩下最小值。

由于数字会重复出现，我们可以同时改变多个最大值和最小值代替模拟一次次操作，以此减轻时间复杂度。

2. 时间复杂度分析

最坏情况：当

N=10^6

，且每一个数不一样，每次同时改变

1

个最大值和

1

个最小值，需要操作

\frac{N-2}{2}=499,999

次，不难看出时间复杂度为

O(n)

，简直完美。

3. 代码细节

由于题目优先改变最大值，所以要注意当仅有 $1$ 个最大值和 $2$ 种不同的数时，无需同时与最小值一起改变，只需单独改变最大值即可。（详情见代码特判部分）
十年 OI 一场空，不开 long long 见祖宗。当 $N=10^6$ 且每一个数不一样时，答案约为 $2\sum_{i=1}^{\frac{N-2}{2}}i=2\times\frac{(5\times 10^5-1)\times5\times10^5}{2}$ $=25\times10^{10}-5\times10^5$ 明显超过 int 类型的最大值 $2^{31}-1$ 即 $2147483647$ ，所以使用 long long 存答案。

代码:

CPP

#include<bits/stdc++.h>
#define int long long //无脑 long long 太爽了
using namespace std;
const int N = 1e6+5;
int n, m, idx, ans, vis[N];
struct node{
	//x为数值 t为次数的出现次数
	int x, t;
} a[N];
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> m;
		vis[m]++; //同标记出现次数
	}
	for(int i = 1; i <= 1e6; i++){
		//用vis数组维护a
		if(vis[i]) idx++, a[idx].x = i, a[idx].t = vis[i];
	}
	int l = 1, r = idx;
	while(r-l+1 >= 3){
		int tmp = min(a[l].t, a[r].t); //取左右出现次数最小值
		a[l].t -= tmp, a[l+1].t += tmp, ans += tmp; //左边减去最小值，并维护ans
		if(a[l].t == 0){ //当 a[l].t > a[r].t 时减去剩余的
			l++;
			if(r-l+1 < 3){//特判
				ans+= tmp-1;
				break;
			}
		}
		//右边同理
		a[r].t -= tmp, a[r-1].t += tmp, ans += tmp;
		if(a[r].t == 0){
			r--;
			if(r-l+1 < 3) break;
		}
	}
	cout << ans << ' ' << a[l].x << ' ' << a[r].x; //输出答案，收工~
	return 0;
}

B4274 数字游戏题解

文章操作

B4274 数字游戏

1. 思路分析

题目大意：

2. 时间复杂度分析

3. 代码细节

代码:

相关推荐

评论

B4274 数字游戏题解