CF335F Buy One, Get One Free

\(\text{Solution}\)

其实不想写（因为不好写。。。

所以贴贴 \(\text{Solution}\)

然而就关于这题而言讲得也不太清楚

可撤销贪心就是维护当前状态的最优解，同时考虑以后的反悔

顺着题解，本题在 \(k<val\) 时必然换一种购买方式

而当 \(k\ge val\) 时，有两种方式，一种可能使当前解更优，但另一种却可以留下两次免费获取的机会

所以令 \(res=2val-k\)，压入堆中，对应当前解更优

而 \(res\) 以后可以被弹出，更改之前的决策，在当前免费取两次进而获得当前更优解

然而贴 \(\text{Code}\) 的原因是本人手打了个堆（几千年以来的壮举

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#include <algorithm>

#define IN inline

using namespace std;

typedef long long ll;

const int N = 5e5 + 5;

int n, a[N], b[N], c[N], d[N];

IN void read(int &x) {

	x = 0; char ch = getchar(); int f = 1;

	for(; !isdigit(ch); f = (ch == '-' ? -1 : f), ch = getchar());

	for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());

	x *= f;

}

struct Heap {

	int d[N], siz;

	IN Heap() {siz = 0;}

	IN void Up(int x) {while (x > 1 && d[x] < d[x >> 1]) swap(d[x], d[x >> 1]), x >>= 1;}

	IN void Down(int x) {

		int y = (x << 1);

		while ((y <= siz && d[x] > d[y]) || (y < siz && d[x] > d[y + 1])) {

			if (y < siz && d[y] > d[y + 1]) ++y;

			swap(d[x], d[y]), x = y, y = (x << 1);

		}

	}

	IN int size() {return siz;}

	IN int top() {return d[1];}

	IN void pop() {d[1] = d[siz--], Down(1);}

	IN void push(int x) {d[++siz] = x, Up(siz);}

}Q;

int main() {

	read(n);

	ll ans = 0;

	for(int i = 1; i <= n; i++) read(b[i]), ans += b[i];

	sort(b + 1, b + n + 1), reverse(b + 1, b + n + 1);

	int m = 0;

	for(int i = 1, j; i <= n; i = j + 1) {

		j = i;

		while (j < n && b[j + 1] == b[i]) ++j;

		a[++m] = b[i], c[m] = j - i + 1;

	}

	int num = 0;

	for(int i = 1; i <= m; num += c[i++]) {

		int rest = min(num - Q.size() * 2, c[i]), cnt = 0;

		for(int j = 1; j <= rest; j++) d[++cnt] = a[i];

		rest = c[i] - rest;

		for(int j = 1; j <= rest; j += 2) {

			if (!Q.size()) break;

			int k = Q.top(); Q.pop();

			if (k < a[i]) {d[++cnt] = a[i]; if (j < rest) d[++cnt] = a[i];}

			else {d[++cnt] = k; if (j < rest) d[++cnt] = a[i] * 2 - k;}

		}

		for(int j = 1; j <= cnt; j++) if (d[j] >= 0) Q.push(d[j]);

	}

	while (Q.size()) ans -= Q.top(), Q.pop();

	printf("%lld\n", ans);

}

巴特西

CF335F Buy One, Get One Free

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章