\(\mathcal{Description}\)

合并果子，初始果子的权值在 \(1\sim n\) 之间，权值为 \(i\) 的有 \(a_i\) 个。每次可以挑 \(x\in[L,R]\) 个果子合并成一个，代价为所挑果子权值之和。求合并所有果子的最少代价。\(T\) 组数据。

\(T\le10\)，\(n,a_i\le10^5\)，\(2\le L\le R\le\sum_{i=1}^na_i\)。

\(\mathcal{Solution}\)

把合并考虑成一棵树，树叉在 \([L,R]\) 内，可以发现总代价为每个点的深度 \(\times\) 权值之和。以此为背景证明几个结论（当然很容易直接猜到最终结论）。

Lemma 1：最优解的非叶结点最少。否则，一定可以删除最深的非叶结点，并把它的儿子们丢给其它非叶结点，使“深度 \(\times\) 权值之和”变小。

Lemma 2：记 \(u\) 的深度为 \(d(u)\)，当树满足 Lemma 1 时，若存在非叶结点 \(d(u)<d(v)\)，则 \(u\) 满叉。很显然，只要 \(v\) 存在且 \(u\) 不满，就可以把 \(v\) 的儿子接到 \(u\) 下使答案更优。由此有推论：存在最优解，其合并数量构成的序列字典序最小（先最小（\(L\)），再最大 \(R\)）。

考虑到实际问题，我们可以断言答案的合并数量为：\(\{L,L,\cdots,L,x,R,R,\cdots,R\}\) 且其中 \(R\) 尽可能多。

不过这个题你甚至不能带堆的 \(\log\) qwq！

由输入方式，显然一堆果子可以表示成 \((\text{权值},\text{个数})\) 二元组，初始时有 \(n\) 个二元组（有些个数是 \(0\)，用于占位），它们已按权值升序排列了。考虑从队首取出若干个小果子合并成大果子，显然和出的大果子的权值是升序的，那么很多情况下大果子可以直接插在队尾。不过可能有大果子的权值属于 \([1,n]\) 的情况，我们直接把对应果子的个数 \(+1\) 即可。

复杂度 \(\mathcal O(Tn\log\sum_{i=1}^na_i)\)。（Tiw 说的 qwq。

\(\mathcal{Code}\)

#include <queue>

#include <cstdio>

#include <iostream>

typedef long long LL;

typedef std::pair<LL, LL> pll;

inline char fgc () {

	static char buf[1 << 17], *p = buf, *q = buf;

	return p == q && ( q = buf + fread ( p = buf, 1, 1 << 17, stdin ), p == q ) ? EOF : *p ++;

}

inline LL rint () {

	LL x = 0; char s = fgc ();

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

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

	return x;

}

const int MAXN = 1e5;

int n, a[MAXN + 5];

LL L, R, S, ans;

std::queue<pll> plan;

struct GreadyQueue {

	std::deque<pll> deq;

	std::deque<pll>::iterator ptr;

	GreadyQueue (): ptr ( deq.end () ) {}

	inline void clear () { deq.clear (), ptr = deq.end (); }

	inline pll& front () { return deq.front (); }

	inline void popF () {

		bool eff = ptr == deq.begin ();

		deq.pop_front ();

		if ( eff ) ptr = deq.begin ();

	}

	inline void add ( const pll x ) {

		ans += x.first * x.second;

		for ( ; ptr != deq.end () && ptr->first < x.first; ++ ptr );

		if ( ptr == deq.end () ) deq.push_back ( x ), -- ( ptr = deq.end () );

		else ptr->second += x.second;

	}

} Q;

inline void clear () {

	ans = S = 0, Q.clear ();

	for ( ; !plan.empty (); plan.pop () );

}

inline bool calcPlan () {

	LL tR = ( S - 1 ) / ( R - 1 ) + !!( ( S - 1 ) % ( R - 1 ) ), tL = 0;

	if ( tR * ( L - 1 ) > S - 1 ) return false;

	LL def = tR * ( R - 1 ) - ( S - 1 );

	if ( L ^ R ) {

		tR -= tL = def / ( R - L ), def -= tL * ( R - L );

		if ( tL ) plan.push ( pll ( L, tL ) );

		if ( def ) plan.push ( pll ( R - def, 1 ) ), -- tR;

	}

	if ( tR ) plan.push ( pll ( R, tR ) );

	return true;

}

inline void followPlan () {

	for ( ; !plan.empty (); plan.pop () ) {

		pll stp ( plan.front () ), cur ( 0, 0 );

		while ( stp.second ) {

			if ( cur.second ) {

				if ( cur.second + Q.front ().second >= stp.first ) {

					cur.first += Q.front ().first * ( stp.first - cur.second );

					Q.front ().second -= stp.first - cur.second;

					Q.add ( pll ( cur.first, 1 ) ), cur = pll ( 0, 0 );

					-- stp.second;

				} else {

					cur.first += Q.front ().second * Q.front ().first;

					cur.second += Q.front ().second, Q.popF ();

					continue;

				}

			}

			LL cnt = std::min ( stp.second, Q.front ().second / stp.first );

			if ( cnt ) Q.add ( pll ( Q.front ().first * stp.first, cnt ) );

			stp.second -= cnt, Q.front ().second -= stp.first * cnt;

			if ( stp.second ) {

				cur = pll ( Q.front ().second * Q.front ().first, Q.front ().second );

				Q.popF ();

			}

		}

	}

}

int main () {

	freopen ( "river.in", "r", stdin );

	freopen ( "river.out", "w", stdout );

	for ( int T = rint (); T --; ) {

		clear ();

		n = rint (), L = rint (), R = rint ();

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

			Q.deq.push_back ( pll ( i, a[i] = rint () ) );

			S += a[i];

		}

		if ( !calcPlan () ) { puts ( "-1" ); continue; }

		Q.ptr = Q.deq.begin (), followPlan ();

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

	}

	return 0;

}

\(\mathcal{Details}\)

用 std::deque 是因为只有它有迭代器啦 owo。

涉及容器元素变化（特别是 pop，erase 之类）的时候，特别注意迭代器的操作嗷！

巴特西

Solution -「LOCAL」Drainage System

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

\(\mathcal{Details}\)

最新文章

热门文章