JZOJ5432. 三元组

题目大意

\(X+Y+Z\)个三元组, 分别为\((x_i, y_i, z_i)\), 每个三元组可以选取一个加到总贡献中, 要求选取\(x\)的有\(X\)个, 选取\(y\)的有\(Y\)个, 选取\(z\)的有\(Z\)个, 求最大总贡献.
设\(n=X+Y+Z\), 则\(n<=500000\).
对于\(10\%\)的数据, \(X=0\).

解题思路

考虑部分分. 如果\(X=0\), 怎么做呢? 这个时候三元组就是二元组了对吧, 那么最优的做法一定是: 把原数列按照\(y_i-z_i\)从大到小排序, 前\(Y\)个选\(y\), 后\(Z\)个选\(z\).
现在有了一个\(X\), 又怎么办呢? 不妨还是这样排序(因为总体上排完序以后, 虽然多了\(X\), 但是选\(Y\)的总体还是在\(Z\)的前面), 考虑如何选\(X\).
枚举\(Y\)和\(Z\)的分界线(分界线左端, 只会有选\(X\)和\(Y\)的三元组, 分界线右端, 只会有选\(X\)和\(Z\)的三元组), 在分界线从左到右移动的时候, 会有一个一个的数的贡献改变, 设移动的数的下标为\(i\), 我们从左右两边分开分析.

左边 : 主要问题是考虑新加进来的数是选\(X\)还是选\(Y\). 类似分析\(Y\)和\(Z\)的方法, 只需任意的\(j\in{Y}\)满足\(y_i-x_i>y_j-x_j\), 那么\(i\)就能把\(j\)从\(Y\)中替换出来(贡献更优). 不难发现只要用堆维护\(y_j-x_j\)的最小值即可判断是否能替换. (代码中维护了\(x_j-y_j\)的最大值, 本质上一样.)

右边 : 主要问题是考虑删去的数对于答案的影响. 若\(i\in{Z}\), 就需要从\(X\)中补一个数给\(Z\)(否则直接减去\(x_i\)即可), 那么补给\(Z\)的数要是最优的, 即\(z_j-x_j\)最大的数. 这个也能用堆维护.

综上, 用\(O(n\log{n})\)的时间复杂度通过了本题.

后记

自己用\(\text{STL}\)的常数还是太大了, 尝试用了\(\text{pb_ds}\)的配对堆, 开了石家庄\(\text{O3}\)和LZC快读和LZC\(\text{O3}\), 加上一堆奇怪的优化, 最后在稳定的评测机上连交四次终于从\(55\)分到了\(100\)分... 实际上这题是有线性做法的所以不要学我(

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
#define N 500010
#define re register
#define ll long long
#define init(a, b) memset(a, b, sizeof(a))
#define fo(i, a, b) for(re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for(re int i = (a); i >= (b); --i)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
	x = 0;
	char ch = 0,w = 0;
	for(;ch < ‘0‘ || ch > ‘9‘;w |= ch == ‘-‘,ch = gc());
	for(;ch >= ‘0‘ && ch <= ‘9‘;x = (x << 3) + (x << 1) + (ch ^ ‘0‘),ch = gc());
	w && (x = -x);
}
using namespace __gnu_pbds;
inline ll max(ll a, ll b){return a > b ? a : b;}
struct Node{int x, y, z;}a[N];
int n, nx, ny, nz;
ll ans1, ans2, ans;
bool inz[N];
priority_queue<int> h1;
struct Q
{
	int w, v;
	Q(){w = v = 0;}
	Q(int _w, int _v){w = _w, v = _v;}
	inline bool operator<(const Q b) const
	{
		return v < b.v;
	}
};
priority_queue<Q> h2;
inline bool cmp(Node a, Node b){return a.y - a.z > b.y - b.z;}
int main()
{
	freopen("triple.in", "r", stdin);
	freopen("triple.out", "w", stdout);	
	read(nx), read(ny), read(nz);
	n = nx + ny + nz;
	fo(i, 1, n)	read(a[i].x), read(a[i].y), read(a[i].z);
	std::sort(a + 1, a + n + 1, cmp);
	fo(i, 1, ny)	h1.push(a[i].x - a[i].y), ans1 += a[i].y;
	fo(i, ny + 1, n)	h2.push(Q(i, a[i].z - a[i].x)), ans2 += a[i].x;
	fo(i, 1, nz)
	{
		Q t = h2.top(); h2.pop();
		inz[t.w] = 1; ans2 += t.v;
	}
	ans = ans1 + ans2;
	re int lim = nx + ny;
	fo(i, ny + 1, lim)
	{
		if(inz[i])
		{
			ans2 -= a[i].z;
			while(h2.top().w < i)	h2.pop();
			Q t = h2.top(); h2.pop();
			ans2 += t.v; inz[t.w] = 1;
		}
		else ans2 -= a[i].x;
		if(a[i].x - a[i].y < h1.top())     // if the new one choose y is better than choose x
		{
			re int t = h1.top(); h1.pop(); h1.push(a[i].x - a[i].y);
			ans1 += (ll)a[i].y + t;
		}
		else ans1 += a[i].x;
		ans = max(ans, ans1 + ans2);
	}
	printf("%lld", ans);
	return 0;
}

JZOJ5432. 三元组

原文：https://www.cnblogs.com/Martin-MHT/p/14300051.html