博客主页:PH_modest的博客主页
当前专栏:每日一题
其他专栏:
每日反刍
* C++跬步积累
* C语言跬步积累
座右铭:广积粮,缓称王!
一.题目描述
题目大意:
———————————————————————————————————————————
给你一个整数数组 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( 0 ≤ a i ≤ 1 0 9 0 \le a_i \le 10^9 0≤ai≤109 )。在一次操作中,你可以选择一个整数 x x x ( 0 ≤ x ≤ 1 0 18 0 \le x \le 10^{18} 0≤x≤1018 ),并用 ⌊ a i + x 2 ⌋ \lfloor \frac{a_i + x}{2} \rfloor ⌊2ai+x⌋ 替换 a i a_i ai ( ⌊ y ⌋ \lfloor y \rfloor ⌊y⌋ 表示将 y y y 舍入为最接近的整数)。 ⌊ y ⌋ \lfloor y \rfloor ⌊y⌋ 表示将 y y y 舍入为最接近的整数)来替换从 1 1 1 到 n n n 的所有 i i i 。请注意,每次操作都会影响数组中的所有元素。
打印使数组中所有元素相等所需的最小操作数。
如果操作次数小于或等于 n n n ,则打印每次操作所选择的 x x x 。如果有多个答案,则打印任意一个。
———————————————————————————————————————————
题目链接:
C. Add, Divide and Floor(Educational Codeforces Round 158 (Rated for Div. 2))
二.思路分析
通过样例自己模拟一遍之后可以发现,操作之后每个数的相对大小关系不会变,由此可以想到我们只需要维护好最大值和最小值,只要他们两个最后相等,其余的值肯定也相等
然后再根据奇偶性关系,找出对应的x
-
结论:
- 最小值为奇数,最大值为奇数:任意数
- 最小值为偶数,最大值为偶数:任意数
- 最小值为奇数,最大值为偶数:x取奇数(这边为了方便直接写成1)
- 最小值为偶数,最大值为奇数:x取偶数(这边为了方便直接写成0)
所以只需要循环操作,使得最大值与最小值相等即可,每次x取得值放入数组中(注意x每次取得值不一样,一开始以为只需要考虑一次就够了,结果WA2 O.o)
三.代码展示
//https://codeforces.com/contest/1901/problem/C
//操作之后每个数的相对大小关系不会改变,因此只需要考虑最大值和最小值,当他们两个相同时其余的数也都相同
//
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
int s[200020];
int v[200020];
void solve()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
sort(s,s+n);
int maxx=s[n-1];
int minn=s[0];
int ans=0;
int x=0;
int r=0;
while(minn!=maxx)
{
if(minn%2==0&&maxx%2==0||minn%2==1&&maxx%2==1)
{
v[r++]=1;
}
else if(minn%2==0&&maxx%2==1)
{
v[r++]=0;
}
else
{
v[r++]=1;
}
minn=(minn+v[r-1])/2;
maxx=(maxx+v[r-1])/2;
ans++;
}
if(ans<=n)
{
cout<<ans<<"\n";
for(int i=0;i<ans;i++)
{
cout<<v[i]<<" ";
}
cout<<"\n";
}
else
{
cout<<ans<<"\n";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
最后:
每日一题系列旨在养成刷题的习惯,所以对代码的解释并不会特别详细,但足够引导大家写出来,选的题目都不会特别难,但也不是特别简单,比较考验大家的基础和应用能力,我希望能够将这个系列一直写下去,也希望大家能够和我一起坚持每天写代码。
之后每个星期都会不定期更新codeforces和atcoder上的题目,想要学习算法的友友们千万别错过了,有什么疑问欢迎大家在评论区留言或者私信博主!
在这里送大家一句话:广积粮,缓称王!
文章评论