\(\mathcal{Description}\)

给定升序序列 \(\{x_n\}\) 以及整数 \(k\)，在 \(\{x_n\}\) 中选出恰 \(k\) 对 \((x_i,x_j)\)，使得不存在某个值出现次数多于一次，并最小化 \(\sum|x_i-x_j|\)。

\(\mathcal{Solution}\)

告诉我，你有一个错误的贪心 owo！

显然 \((x_i,x_j)\) 是相邻的两个数。令 \(a_i=x_{i+1}-x_i\)，问题转化为选 \(k\) 个 \(a_i\) 使其和最小，并保证 \(a_i\) 被选后 \(a_{i-1}\) 和 \(a_{i+1}\) 不被选。

贪心取最小是不可取的，样例就是反例。不过可以使用网络流退流的思想挽救这个贪心。每次取出最小值 \(a_i\) 时，将 \(a_i\) 的值置为 \(a_{i-1}+a_{i+1}-a_i\) 并重新入堆，同时删除在序列上 \(a_{i-1}\) 和 \(a_{i+1}\)（这里的下标加减法指前驱后继，因为有些数已经被删掉了）。考虑再次选择 \(a_i\) 时所表达的方案：

初始：

\[\require{cancel}a_{i-2}~~~~a_{i-1}~~~~a_i~~~~a_{i+1}~~~~a_{i+2}
\]

选 \(a_i\)，此时答案 \(ans=a_i\)；并重置 \(a_i\)，删前驱后继：

\[\require{cancel}a_{i-2}~~~~\cancel{a_{i-1}}~~~~a_{i-1}+a_{i+1}-a_i~~~~\cancel{a_{i+1}}~~~~a_{i+2}
\]

再选 \(a_i\)，此时答案 \(ans=a_i+a_{i-1}+a_{i+1}-a_i=a_{i-1}+a_{i+1}\)，再重置，删除：

\[\require{cancel}\cancel{a_{i-2}}~~~~\cancel{a_{i-1}}~~~~a_{i-2}+a_{i+2}-a_{i-1}-a_{i+1}+a_i~~~~\cancel{a_{i+1}}~~~~\cancel{a_{i+2}}
\]

可以发现，这与直接选 \(a_{i-2}\) 和 \(a_{i+2}\) 是等效的！所以维护一个双向链表，利用堆进行贪心即可。

复杂度 \(\mathcal O(n\log n)\)。

\(\mathcal{Code}\)

#include <queue>

#include <cstdio>

typedef long long LL;

typedef std::pair<LL, int> pli;

const int MAXN = 1e5;

int n, K, pre[MAXN + 5], suf[MAXN + 5];

LL val[MAXN + 5];

bool rmd[MAXN + 5];

std::priority_queue<pli, std::vector<pli>, std::greater<pli> > heap;

inline int rint () {

	int x = 0; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}

inline void rmpos ( const int u ) {

	if ( ! u || u == n ) return ;

	rmd[u] = true;

	if ( pre[u] ) suf[pre[u]] = suf[u];

	if ( suf[u] ^ n ) pre[suf[u]] = pre[u];

	pre[u] = suf[u] = 0;

}

int main () {

	n = rint (), K = rint ();

	for ( int i = 0, p, las; i < n; ++ i ) {

		p = rint ();

		if ( i ) {

			heap.push ( { val[i] = p - las, i } );

			pre[i] = i - 1, suf[i] = i + 1;

		}

		las = p;

	}

	LL ans = 0;

	val[0] = val[n] = 1ll << 60;

	while ( K -- ) {

		pli t = heap.top (); heap.pop ();

		if ( rmd[t.second] ) { ++ K; continue; }

		ans += t.first; LL nv = -t.first;

		nv += val[pre[t.second]], rmpos ( pre[t.second] );

		nv += val[suf[t.second]], rmpos ( suf[t.second] );

		heap.push ( { val[t.second] = nv, t.second } );

	}

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

	return 0;

}

巴特西

Solution -「APIO/CTSC 2007」「洛谷 P3620」数据备份

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章