P9667 [ICPC 2022 Jinan R] Tower
题目描述
庞教授搭了nnn座不同高度的塔。第iii座塔的高度是aia _ {i}ai。
寿教授不喜欢这些参差不齐的塔。他决定先去掉它们中的mmm座，然后执行以下操作中的一些（或不执行）：
- 选择一座塔并增加它111个单位高度。
- 选择一座塔并减少它111个单位高度。
- 选择一座塔并把它的高度aia _ {i}ai除以222，如果它不是整数的话，向下取整。
寿教授永远不会选择被拆除的塔。如果操作后，塔的高度变为000，则不允许操作。在这些约束条件下，寿教授可以按任意顺序执行任意数量的运算。
寿教授希望所有没有被拆除的塔都有相同的高度aia _ {i}ai。请计算实现此目标的最小操作次数。
输入格式
第一行是一个整数T(1⩽T(1\leqslantT(1⩽TTT⩽\leqslant⩽10)10)10),表示有TTT组数据。
对于每组测试数据，第一行包括两个整数n,m(1⩽n,m (1\leqslantn,m(1⩽nnn⩽\leqslant⩽500500500,000⩽\leqslant⩽mmm⩽n\leqslant n⩽n)，表示塔的数量以及寿教授在执行操作之前应该删除的塔的数量。
下一行包括nnn个整数a1,…,an(1⩽a _ {1},\dots,a _ {n} (1\leqslanta1,…,an(1⩽aia _ {i}ai⩽\leqslant⩽109)10^9)109)，表示塔的最初高度。
输出格式
对于每组测试数据，在一行中输出最小操作数。
输入输出样例 #1
输入 #1
3 2 0 2 6 5 0 1 2 3 4 5 5 3 1 2 3 4 5输出 #1
2 4 1C++实现
#include<bits/stdc++.h>usingnamespacestd;#defineN505#defineintlonglongintn,m,i,j,ans,a[N],t,s[N];vector<int>G;signedmain(){scanf("%lld",&t);while(t--){G.clear();scanf("%lld%lld",&n,&m),ans=1e9;for(i=1;i<=n;i++)scanf("%lld",&a[i]);for(i=1;i<=n;i++){intk=a[i];while(k){G.push_back(k);k>>=1;}}for(inty:G){for(i=1;i<=n;i++)s[i]=1e9;for(i=1;i<=n;i++){intk=a[i],cnt=0;while(k>=1){s[i]=min(s[i],cnt+abs(k-y));k>>=1,cnt++;}}sort(s+1,s+1+n);intsum=0;for(i=1;i<=n-m;i++)sum+=s[i];ans=min(ans,sum);}printf("%lld\n",ans);}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
