专栏文章

CF2171B Yuu Koito and Minimum Absolute Sum

AAndy1101
CF2171B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqprow5
此快照首次捕获于
2025/12/04 08:44
3 个月前
此快照最后确认于
2025/12/04 08:44
3 个月前
查看原文
题目传送门

题目大意

定义一个数组 bi=ai+1−aib_i=a_{i+1}-a_i。你需要用非负整数替换 aa 数组中的所有 −1-1，使得在 ∑i=1n−1bi\sum\limits_{i=1}^{n-1}b_i 的绝对值最小的前提下让数组 aa 的字典序最小。即在 ∣b1+b2+…bn−2+bn−1∣\left|b_1+b_2+ \dots b_{n-2}+b_{n-1}\right| 最小的前提下让数组 aa 的字典序最小。

思路

因为 b1=a2−a1 , b2=a3−a2 , b3=a4−a3 , … , bn−2=an−1−an−2 , bn−1=an−an−1b_1=a_2-a_1 \ ,\ b_2=a_3-a_2 \ ,\ b_3=a_4-a_3 \ ,\ \dots \ ,\ b_{n-2}=a_{n-1}-a_{n-2} \ ,\ b_{n-1}=a_n-a_{n-1}，所以我们可以看出 ∑i=1n−1bi=an−a1\sum\limits_{i=1}^{n-1}b_i=a_n-a_1。也就是说答案只与 ana_n 和 a1a_1 有关，而且为了保证字典序最小，将其余的未知数都赋值为 00 即可。这时候我们就可以分成四种情况来讨论。
  1. 当 a1a_1 和 ana_n 都未知时，将 a1a_1 和 ana_n 都赋值为 00（因为要保证字典序最小，所以要赋值为 00），最小值为 00。
  2. 当 a1a_1 未知，ana_n 已知时，将 a1a_1 赋值为 ana_n 的值，最小值为 00。
  3. 当 a1a_1 已知，ana_n 未知时，将 ana_n 赋值为 a1a_1 的值，最小值为 00。
  4. 当 a1a_1 和 ana_n 都已知时，最小值为 ∣an−a1∣\left|a_n-a_1\right|。
随后输出数组 aa 即可。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+4;
int a[N]; 
void solve()
{
	int n;
	cin >>n;
	for(int i=1;i<=n;i++) cin >>a[i];
	if(a[1]!=-1 && a[n]!=-1)
	{
		cout <<abs(a[n]-a[1])<<'\n'; 
		for(int i=1;i<=n;i++)
		{
			if(a[i]==-1) cout <<0<<" ";
			else cout <<a[i]<<" ";
		}
	}
	else if(a[1]==-1 && a[n]!=-1)
	{
		cout <<0<<'\n';
		for(int i=1;i<=n;i++)
		{
			if(i==1) cout <<a[n]<<" ";
			else if(a[i]==-1) cout <<0<<' ';
			else cout <<a[i]<<' ';
		}
	}
	else if(a[1]!=-1 && a[n]==-1)
	{
		cout <<0<<'\n';
		for(int i=1;i<=n;i++)
		{
			if(i==n) cout <<a[1]<<" ";
			else if(a[i]==-1) cout <<0<<" ";
			else cout <<a[i]<<" ";
		}
	}
	else
	{
		cout <<0<<"\n";
		for(int i=1;i<=n;i++)
		{
			if(a[i]==-1) cout <<0<<" ";
			else cout <<a[i]<<" ";
		}
	}
	cout <<'\n';
}
int main()
{
	    
	int t;
	cin >>t;
	while(t--) solve();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...