CF2154C

你说得对。但是无论什么代价都在所不惜。（题目名字）

题面

有一个长度为

n

的序列

a

，对于每个位置

i

，对其进行

+1

操作的代价是

b_{i}

。求最小的代价，使得序列

a

中存在不互质的两个数。

对于这一题的简单版：

b_{i}=1

。

对于这一题的困难版：

1 \le b_{i} \le 10^9

。

题解

妙妙贪心思维题，从简单版开始想。

首先，特判本来已有一对不互质的数的情况。具体地，对于每个

a_{i}

对其分解质因数，然后开个桶

f_{x}

存质数

x

是否存在于

a

中，

f_{x}=1

则

x

存在。若重复覆盖到一个点，则输出

0

。

接着，对数列的性质进行观察：两个数

a_{i},a_{j}

均为奇数，则花费

b_{i}+b_{j}

代价将二者均

+1

，使得其均为偶数。这便是答案的上界。若对两个及以上的数进行多次操作，明显不优于上述情况。

于是，对

b

排序。

此时只有对一个数进行操作的情况了。

在简单版中，很明显，一个数至多进行一次

+1

操作，对一个数进行大于

1

次

+1

显然不优于把两个数都进行一次

+1

的情况。具体地，从小到大枚举，对每个数

a_{i}

进行

+1

操作后分解质因数，同样若覆盖到

f_{x}=1

的地方，那么答案就为把这一个位置

+1

的代价，也就是

b_{i}

。

困难版中，将一个数从

+1

一次推广到

+1

多次的情况：

对于 $b_{i}$ 大于 $b_{1}+b_{2}$ 的位置 $i$ ，对其进行操作肯定不优。
对于 $b_{i}$ 大于 $b_{1}$ 的位置 $i$ ，对其至多进行一次 $+1$ 操作。证： $b_{2} \ge b_{1}$ 且 $b_{2}$ 是 $\ge b_{1}$ 中最小的值，若 $b_{i}>b_{1}$ ，则有 $b_{i} \ge b_{2}$ ，因此 $2 \times b_{i} \ge b_{2}+b_{1}$ 。
对于 $b_{i}$ 等于 $b_{1}$ 的位置，可以进行多次操作。枚举所有 $f_{x}=1$ 的 $x$ ，然后算使 $a_{i}$ 变为 $x$ 的倍数的最小代价。

做到这一步，你最终会发现：Time limit exceeded on test 23。

~~我想了一堆法子优化都被卡死了，这是算法出了问题！~~

仔细思考，就可以发现出题人可以构造一堆

b_{i}=b_{1}

卡掉。这种情况下怎么做呢？

构造了一堆

b_{i}=b_{1}

……那么它不就退化到了类似简单版中，所有值均为

1

的情况了吗？！此时加两个的代价为

b_{1}+b_{2}= 2 \times b_{1}

，只有对

b_{i} \le 2 \times b_{1}

的地方

+1

会更优！

把上面这个判掉，此时就只用判对第一个位置加多次了！

此题完结。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int _;
int n;
struct node {
	int a,id;
	int b;
} s[N];
int f[N];
int prime[N];
int minp[N],cnt;
int num,p[N];
int ct;
ll ans;
bool cmp(node x,node y) {
	return x.b<y.b;
}
inline int get() {
	char ch=getchar();
	int x=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x;
}
inline void solve() {
	ans=-1ll,ct=num=0;
	memset(f,0,sizeof f);
	n=get();
	for(int i=1;i<=n;i++) {
		s[i].a=get();
		if(~ans) continue;
		int x=s[i].a;
		if(x==1) continue;
		for(int j=minp[x];x>1;j=minp[x]) {
			if(x%j==0) {
				if(f[j]) {ans=0;break;}
				f[j]=1,p[++num]=j;
				while(x%j==0) x/=j;
			}
		}
	}
	for(int i=1;i<=n;i++) s[i].b=get();
	if(~ans) {puts("0");return;}
	sort(s+1,s+1+n,cmp),sort(p+1,p+1+num);
	ans=s[1].b+s[2].b;
	bool flag=false;
	for(int i=1;i<=n;i++) {
		if(s[i].b>ans) break;
		int x=s[i].a+1;
		for(int j=minp[x];x>1;j=minp[x]) {
			if(x%j==0) {
				while(x%j==0) x/=j;
				if(f[j]) {ans=s[i].b,flag=true;break;}
			}
		}
		if(flag) break;
	}
	if(s[2].b!=s[1].b) {
		for(int j=1;j<=num;j++) {
			if(s[1].a%p[j]==0) continue;
			ll x=p[j]-s[1].a%p[j];
			ans=min(ans,x*s[1].b);
			if(p[j]>s[1].a) break;
		}
	}
	printf("%lld\n",ans);
	return;
}
int main() {
	_=get();
	for(int i=2;i<=N-2;i++) {
		if(!minp[i]) prime[++cnt]=i,minp[i]=i;
		for(int j=1;j<=cnt&&prime[j]*i<=N-2;j++) {
			minp[prime[j]*i]=prime[j];
			if(i%prime[j]==0) break;
		}
	}
	while(_--) solve();
	return 0;
}

文章操作

题面

题解

代码

相关推荐

评论

CF2154C