窍门
2025-07-01 09:20:38
发布于:江苏
4阅读
0回复
0点赞
首先,由于%3魔法可以无限使用,这就帮我们排除了所有3的倍数,因为它们都可以变为0
那我们要考虑的其实是非3倍数
题中所给的第二种魔法中,其实有一个小窍门:
将一个数变为平方减1,也就是将x变为x^2 -1,根据平方差公式可得x^2 -1=(x+1)(x-1),由于x为非3倍数,因此x+1与x-1中必有一个为3倍数,那也就是说x^2 -1必为3倍数,配合第一个魔法,可以直接变成0。
所以+1魔法甚至根本不需要,只要按余数大小排个序,再删掉用第二个魔法后收益最大的前k个即可。
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1005],s,t,b[1005];
bool cmp(int x,int y){
return x%3>y%3;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]%3!=0){
b[++t]=a[i];
}
}
sort(b+1,b+1+t,cmp);
for(int i=k+1;i<=t;i++){
s+=b[i]%3;
}
cout<<s;
return 0;
}
这里空空如也
有帮助,赞一个