2
XV Olimpiada Informatyczna - Etap 1 - klo
source link: http://maskray.me/blog/2010-03-13-xv-olimpiada-informatyczna-etap-1-klo
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
XV Olimpiada Informatyczna - Etap 1 - klo
题目大意：有一个长为 N 的整数数列，每次可以把一个数增减一，求最少次数使得有连续 K 个数相同。
下面程序用 Size balanced tree 实现，卫星数据是子树节点数和子树关键字和。
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
const int N = 100000;
int a[N];
struct Node *null, *pit, *root;
struct Node
int key, size;
long long sum;
Node *ch[2];
Node() {}
Node(int key) : key(key), size(1), sum(key) {ch[0] = ch[1] = null; }
void update() {
size = ch[0]->size + 1 + ch[1]->size;
sum = ch[0]->sum + key + ch[1]->sum;
}pool[N+1];
void zag(Node *&x, int d)
Node *y = x->ch[!d];
x->ch[!d] = y->ch[d];
y->ch[d] = x;
y->size = x->size;
y->sum = x->sum;
x->update();
void maintain(Node *&x, int d)
if (x == null) return;
if (x->ch[d]->ch[d]->size > x->ch[!d]->size)
zag(x, !d);
else if (x->ch[d]->ch[!d]->size > x->ch[!d]->size)
zag(x->ch[d], d), zag(x, !d);
else return;
maintain(x->ch[0], 0);
maintain(x->ch[1], 1);
maintain(x, 0);
maintain(x, 1);
void insert(Node *&x, int key)
if (x == null) {
x = new Node(key);
return;
int d = x->key < key;
++x->size;
x->sum += key;
insert(x->ch[d], key);
maintain(x, d);
Node *erase(Node *&x, int key)
if (x->key == key || key < x->key && x->ch[0] == null || key > x->key && x->ch[1] == null) {
if (x->ch[0] == null || x->ch[1] == null) {
Node *y = x;
x = x->ch[x->ch[0] == null];
return y;
Node *y = erase(x->ch[1], key-1);
x->key = y->key;
x->update();
return null;
Node *y = erase(x->ch[x->key < key], key);
x->update();
return y;
long long tot, mid;
void count(Node *&x, int cnt)
if (x->ch[0]->size == cnt) {
mid = x->key;
tot += x->ch[0]->sum + x->key;
} else if (x->ch[0]->size > cnt)
count(x->ch[0], cnt);
tot += x->ch[0]->sum + x->key,
count(x->ch[1], cnt-x->ch[0]->size-1);
int main()
pit = pool;
root = null = new Node(0); null->size = 0; null->ch[0] = null->ch[1] = null;
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
long long best = LLONG_MAX;
int res1, res2, res3;
for (int i = 0; i < k-1; i++)
insert(root, a[i]);
for (int i = k-1; i < n; i++) {
insert(root, a[i]);
tot = 0;
count(root, k/2);
long long t = mid*(k/2+1)-tot + root->sum-tot-mid*(k-k/2-1);
if (t < best) {
best = t;
res1 = i-k+1;
res2 = i;
res3 = mid;
erase(root, a[i-k+1]);
printf("%lld\n", best);
for (int i = res1; i <= res2; i++)
a[i] = res3;
for (int i = 0; i < n; i++)
printf("%d\n", a[i]);
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK