【枚举+结论】icpc2022 济南 A

╰+攻爆jí腚メ 2024-03-22 23:07 76阅读 0赞

[Problem - A - Codeforces][]

题意：

![57d5c493fcec44d2a7b7cfc37938be39.png][]

思路：

本来的思路是这样的

考虑最后会变成什么数，手摸了几个发现，都是2，不论本来的集合是不是包含2

然后就是猜测是不是直接变成2就好了

然后要去掉m个，直接考虑去掉最大的m个

这样是wa2的

然后考虑去枚举最后变成什么数，猜测最后会变成集合中本来有的数，也wa2了

首先第一个，最后变成的数，一定是集合中某个数/2之后的值，这点需要观察到

然后，需要把贡献算出来之后再去排序，去掉排序后的m个大的，这里也有点问题，应该把贡献算出来了之后再去排序

其实错误的思路都有个共同点，就是猜了结论之后没有去想为什么，在想为什么的过程其实就是pushup归纳的过程

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e3+10;
    const int mxe=5e5+10;
    
    int N,M;
    int a[mxn];
    
    int calc(int u,int k){
    	//u变成k的最少操作次数
    	if(u<=k) return k-u;
    	else{
    		int tu=u;
    		int cnt=0;
    		while(tu/2>=k){
    			cnt++;
    			tu/=2;
    		}
    		int tmp=cnt+tu-k;
    		if(tu>0){
    			tu/=2;
    			tmp=min(tmp,cnt+1+k-tu);
    		}
    		return tmp;
    	}
    }
    void solve(){
    	cin>>N>>M;
    	set<int> S;
    	for(int i=1;i<=N;i++){
    		cin>>a[i];
    		int x=a[i];
    		while(x){
    			S.insert(x);
    			x>>=1;
    		}
    	}
    	int ans=9e18;
    	for(auto u:S){
    		vector<int> V;
    		for(int i=1;i<=N;i++) V.push_back(calc(a[i],u));
    		sort(V.begin(),V.end());
    		int res=0;
    		for(int i=0;i<N-M;i++) res+=V[i];
    		ans=min(ans,res);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - A - Codeforces]: https://codeforces.com/gym/104076/problem/A
[57d5c493fcec44d2a7b7cfc37938be39.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a5e399c4e40b40b1845019ae1fe3f60a.png