众所周知,本题稍稍转化后就是个线性求中位数,可以用快速选择或值域分块然后大卡常做。

你说得对,但是 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 条评论

  • @ 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
    上传者