题目:给你一个整数数组 a1,a2,…,an 。在一次操作中,你可以选择一个整数 x ,并用 (a[i]+x)/2 替换 ai ( (a[i]+x)/2表示将 y(a[i]+x)/2舍入为最接近的整数(下取整)。 ⌊y⌋ 表示将 y 舍入为最接近的整数)来替换从 1 到 n 的所有 i。请注意,每次操作都会影响数组中的所有元素。打印使数组中所有元素相等所需的最小操作数。如果操作次数小于或等于 n,则打印每次操作所选择的 x 。如果有多个答案,则打印任意一个。
4
1
10
2
4 6
6
2 1 2 1 2 1
2
0 32
0 2 2 5 1 1 6
思路:
将a1~an 进行排序
若 b<=c 则 (b+x)/2<=(c+x>)/2;
类似与夹逼定理的思路 只需要让 a1(最小值)与an(最大值)相等 其余的值都就相等了
即a1=a2=a3=…=an
x取1 3 5 7 …2n+1 进行操作 会让最大值和最小值的差值都一样
x取0 2 4 6 …….2n 进行操作 会让最大值和最小值的差值都一样
那不妨就只取1、0(x的大小不会改变答案,x的奇偶性可以改变答案)
思考什么样的条件下 x取1 什么样的条件下x取0
若x取1 这样让(最小值+x)/2 可以+1 (最大值+1)/2可能+1 也可能+0
若x取0 (最小值+x)/2 +0 (最大值+1)/2可能+1 也可能+0
故取1
若x取1 (最小值+x)/2 +0 (最大值+1)/2可能+1 也可能+0
若x取0 (最小值+x)/2 +0 (最大值+1)/2 +0
故取0
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<ll>v;
map<ll,ll>mp;
ll a[N];
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
ll min1=a[1],max1=a[n];
v.clear();
if(n==1) cout<<"0"<<endl;
else
{
while(min1!=max1)
{
if(min1!=0)
{
if(min1%2!=0)
{
v.push_back(1);
min1=(min1+1)/2;
max1=(max1+1)/2;
}
else
{
v.push_back(0);
min1/=2;
max1/=2;
}
}
else
{
v.push_back(0);
max1/=2;
}
}
cout<<v.size()<<endl;
if(v.size()<=n)
{
for(int i=0;i<v.size();i++)
{
cout<<v[i]<<" ";
}
cout<<endl;
}
}
}
return 0;
}
原文地址:https://blog.csdn.net/m0_74015873/article/details/134617511
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_12677.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!