QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#611739#5137. TowerYinyuDreamWA 12ms3804kbC++202.1kb2024-10-04 22:28:332024-10-04 22:28:36

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 22:28:36]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:3804kb
  • [2024-10-04 22:28:33]
  • 提交

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'