- 均分纸牌
?
- @ 2026-9-28 9:58:54
众所周知,本题稍稍转化后就是个线性求中位数,可以用快速选择或值域分块然后大卡常做。
你说得对,但是 stable_sort 可以直接 A 掉。
WTF?
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <cstdio>
#define int long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
#define MYBUF (1 << 20)
char buf[MYBUF], *p1, *p2;
#define gc() \
(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MYBUF, stdin), p1 == p2) \
? EOF \
: *p1++)
inline long long rd() {
long long x = 0;
char c = gc();
while (c < '0' || c > '9') c = gc();
for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c ^ '0');
return x;
}
char pbuf[MYBUF], *pp = pbuf;
inline void pc(const char &c) {
if (pp - pbuf == MYBUF) fwrite(pbuf, 1, MYBUF, stdout), pp = pbuf;
*pp++ = c;
}
inline void wt(long long x) {
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) pc(sta[--top] + '0');
}
#undef MYBUF
const int N=2e7+7;
int n,a[N],sum,ans,minn=1e18;
inline int labs(int x){
return x<0?-x:x;
}
signed main(){
n=rd();
for(register int i=1;i<=n;++i){
a[i]=rd();
sum+=a[i];
}
int x=sum/n;
for(register int i=1;i<=n;++i) a[i]+=a[i-1]-x;
stable_sort(a+1,a+n+1);
for(register int i=1;i<=n;++i)
ans+=labs(a[i]-a[n/2+1]);
wt(ans);
fwrite(pbuf, 1, pp - pbuf, stdout);
return 0;
}
1 条评论
-
qu_ming_zhen_nan LV 8 @ 2026-9-28 10:00:05
#11 Accepted 9 988ms 230.8 MiB
#12 Accepted 9 978ms 230.6 MiB
😄 3🤣 3👍 3👎 3🤡 2
- 1
信息
- ID
- 82
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 202
- 已通过
- 6
- 上传者