C/C++教程

CF1188D Make Equal

本文主要是介绍CF1188D Make Equal,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题意

给定序列a,要求每次操作给某个元素加上\(2^i\),使得最终序列元素全部相同,求最小操作数

题解

设最终元素为 y,答案就是\(\sum_{i=1}^{n}bit(y-a_i)\),其中定义bit(i)是 i 的二进制下的1的个数

首先发现减号不好维护,\(x=y-a_n\),\(b_i=a_n-a_i\),\(a_n\)是最大值,答案就变成了\(\sum_{i=1}^{n}bit(x+b_i)\)

考虑 dp 并逐位计算贡献,此时若计算到第 i 位,对这一位的贡献造成影响的因素是

  1. x 的第 i 位取值

  2. \(b_j\) 的第 i 位取值

  3. \(x+b_j\)在第 i-1 位的进位

1 在dp时可以分两种情况讨论,2 是确定的,考虑 3 如何快速计算

这个时候发现,第 i-1 位的进位情况与\(b_j\mod2^{i}\)下的大小有关,若按照\(\mod 2^{i}\)降序排序,产生贡献的一定是一段前缀

枚举x第 i 位是多少,根据上一位的进位计算出第 i 位的进位和状态,转移即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+11;
struct st_{
	int b,st;
	friend bool operator<(st_ a,st_ b){return a.st>b.st;}
}a[N];
int n;
int num[N];
int f[61][N];
inline void min_(int &a,int b){a=(a<b?a:b);return;}
inline int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
signed main()
{
	n=read();
	int maxx=0;
	for(int i=1;i<=n;++i) a[i].b=read(),maxx=(maxx>a[i].b?maxx:a[i].b);
	for(int i=1;i<=n;++i) a[i].b=maxx-a[i].b,a[i].st=a[i].b&1;
	sort(a+1,a+n+1);
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=0;i<=59;++i)
	{
		for(int j=1;j<=n;++j) num[j]=num[j-1]+(bool)((1ll<<i)&a[j].b);//,cout<<num[j]<<" ";
//		cout<<endl;
		for(int j=0;j<=n;++j)
		{
			min_(f[i+1][num[j]],f[i][j]+j+num[n]-2*num[j]);
			min_(f[i+1][j+num[n]-num[j]],f[i][j]+num[j]+n-j-(num[n]-num[j]));
		}
		for(int j=1;j<=n;++j) a[j].st=a[j].b&((1ll<<i+1)-1);
//		for(int j=1;j<=n;++j) cout<<a[j].b<<" ";
//		cout<<endl;
		sort(a+1,a+n+1);
	}
	cout<<f[60][0]<<endl;
	return 0;
}
这篇关于CF1188D Make Equal的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!