QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#630795 | #5137. Tower | 7islands# | WA | 143ms | 3596kb | C++17 | 3.0kb | 2024-10-11 20:27:12 | 2024-10-11 20:27:12 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii pair<int,int>
using namespace std;
int a[510],ans[510];
int e[510];
int n,m;
struct node{
int pos,val;
bool operator < (const node a)const{
return val<a.val;
}
}ee[510];
void solve(){
cin>>n>>m;
priority_queue<pii> q;
for(int i = 1;i<=n;i++){
cin>>a[i];
ans[i] = 0;
q.push(make_pair(a[i],i));
}
int cnt = 0;
int res = 1e17;
int l = 1,r = q.top().first;
while(l<=r){
int mid = l+r>>1;
int down=0,up = 0,on = 0;
int t = 0;
for(int i = 1;i<=n;i++){
if(a[i] < mid) down ++;
else if(a[i] > mid) up++;
else on++;
ee[i].val = abs(a[i]-mid) + ans[i];
ee[i].pos = i;
t+=abs(a[i]-mid) + ans[i];
}
sort(ee+1,ee+1+n);
for(int i = n;i>0&&i>n-m;i--){
t -=ee[i].val;
if(ee[i].pos>mid) up--;
else if(ee[i].pos<mid) down--;
else on--;
}
if(t<res) res = t;
if(up<down){
if(up+on<down){
r=mid-1;
}
else break;
}
else if(down<up){
if(down+on<up){
l = mid+1;
}
else break;
}
else break;
}
while(!q.empty()){
int pos = q.top().second;
int val = q.top().first;
q.pop();
if(val == 1) break;
val /= 2;
a[pos] = val;
cnt ++;
q.push(make_pair(val,pos));
ans[pos] ++ ;
int l = 1,r = q.top().first;
while(l<=r){
int mid = l+r>>1;
int down=0,up = 0,on = 0;
int t = 0;
for(int i = 1;i<=n;i++){
if(a[i] < mid) down ++;
else if(a[i] > mid) up++;
else on++;
ee[i].val = abs(a[i]-mid) + ans[i];
ee[i].pos = i;
t+=abs(a[i]-mid) + ans[i];
}
sort(ee+1,ee+1+n);
for(int i = n;i>0&&i>n-m;i--){
t -=ee[i].val;
if(ee[i].pos>mid) up--;
else if(ee[i].pos<mid) down--;
else on--;
}
if(t<res) res = t;
if(up<down){
if(up+on<down){
r=mid-1;
}
else break;
}
else if(down<up){
if(down+on<up){
l = mid+1;
}
else break;
}
else break;
}
}
cout<<res<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
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: 143ms
memory: 3596kb
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 3 436 108 570 636 994 228 656 51
result:
wrong answer 8th numbers differ - expected: '227', found: '228'