QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611739 | #5137. Tower | YinyuDream | WA | 12ms | 3804kb | C++20 | 2.1kb | 2024-10-04 22:28:33 | 2024-10-04 22:28:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
void solve(){
int n,m;
cin>>n>>m;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
if(m+1==n){
cout<<0<<endl;
return;
}
sort(a.begin(),a.end());
set<int> s;
for(int i=0;i<n;i++){
int val=a[i];
while(val){
s.insert(val);
val/=2;
}
}
ll ans=1e18;
int len=n-m,mid=len/2;
for(auto val:s){
vector<pair<int,int>> b(n);
for(int i=0;i<n;i++){
b[i].first=a[i];
while(b[i].first/2>=val){
b[i].first/=2;
b[i].second++;
}
}
sort(b.begin(),b.end());
priority_queue<int> q;
ll sum=0;
vector<ll> pre(n),suf(n);
for(int i=0;i<mid;i++){
q.push(b[i].second-b[i].first);
sum+=b[i].second-b[i].first;
}
for(int i=mid-1;i<n;i++){
pre[i]=sum;
if(b[i].second-b[i].first<q.top()){
sum+=b[i].second-b[i].first-q.top();
q.pop();
q.push(b[i].second-b[i].first);
}
}
while(q.size()){
q.pop();
}
sum=0;
for(int i=n-1;i>=n-mid;i--){
q.push(b[i].second+b[i].first);
sum+=b[i].second+b[i].first;
}
for(int i=n-mid;i>=0;i--){
suf[i]=sum;
if(b[i].second+b[i].first<q.top()){
sum+=b[i].second+b[i].first-q.top();
q.pop();
q.push(b[i].second+b[i].first);
}
}
ll tot=1e18;
if(len%2==1){
for(int i=mid;i<n-mid;i++){
tot=min(tot,pre[i-1]+suf[i+1]+b[i].second);
}
}else{
for(int i=mid-1;i<n-mid;i++){
tot=min(tot,pre[i]+suf[i+1]);
}
}
ans=min(ans,tot);
}
cout<<ans<<endl;
}
int main(){
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3804kb
input:
3 2 0 2 6 5 0 1 2 3 4 5 5 3 1 2 3 4 5
output:
2 4 1
result:
ok 3 number(s): "2 4 1"
Test #2:
score: -100
Wrong Answer
time: 12ms
memory: 3620kb
input:
10 272 118 11 14 49 94 71 62 46 45 74 22 15 36 7 37 27 35 96 85 75 78 76 64 23 59 17 35 71 28 96 82 5 66 2 48 57 31 88 10 61 73 79 23 19 52 39 76 48 98 5 39 48 51 90 90 60 27 47 24 24 56 48 27 39 21 38 18 20 9 62 83 47 15 51 22 73 74 7 80 64 60 86 74 59 7 84 38 99 31 42 60 52 41 63 88 59 90 77 40 68...
output:
454 5 437 108 571 634 993 225 653 53
result:
wrong answer 2nd numbers differ - expected: '3', found: '5'