自动搬运

查看原文

来自洛谷，原作者为

	Azazеl Just the smallest grain in the sands

搬运于2025-08-24 22:19:22，当前版本为作者最后更新于2020-07-29 15:51:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6288 [COCI2016-2017#1] Kralj

题目传送门

P6288

写在前面的废话

$\ \ \ \$今天考试的一道妙妙题，考场上看出来是贪心的，甚至贪心策略都是对的，但没想到这题难点不在贪心策略 ，并且考场上时空双爆，建议蓝/紫。

题解

$\ \ \ \$ 第一部分（洛谷上没有）：$\forall i\le n,a_i=1$ ，即所有 $a_i$ 都为 $1$ 。

$\ \ \ \$ 我们稍微想一想，就会发现，我们安排的精灵是第多少个进入，就会与第几个侏儒战斗，因此就变成一个序列的问题。

$\ \ \ \$ 参考田忌赛马的策略，我们将两个力量序列均升序排列后，依次看现在在队首的精灵能否打败侏儒，如果能则安排它与对应的侏儒对战，否则安排它与战力最强的侏儒战斗，进行消耗。

$\ \ \ \$ 具体来说，将两个力量序列升序排列，对每个序列分别设置指针，判断指针指向的元素的大小关系。若精灵这边较大，则答案 $+1$，指针分别后移，否则单独后移精灵序列的指针即可。

$\ \ \ \$ 然后你就会发现这其实是P1650 田忌赛马的弱化版

$\mathcal{CODE}$ （未单独判断是否满足特殊情况）

#include <cstdio>
#include <algorithm>
using namespace std;
int arr[500005],s1[500005],s2[500005];
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
	for(int i=1;i<=n;i++) scanf("%d",&s1[i]);
	for(int i=1;i<=n;i++) scanf("%d",&s2[i]);
	sort(s1+1,s1+1+n);sort(s2+1,s2+1+n);
	int z1=1,z2=1,ans=0;
	while(z1<=n&&z2<=n)
	{
		if(s1[z1]<s2[z2]) z1++,z2++,ans++;
		else z2++;
	}
	printf("%d",ans);
	return 0;
}

$\ \ \ \$第二部分：

$\ \ \ \$ 刚才其实我们已经找到了本题的贪心策略，每次将能走到当前位置的精灵与现在位置的侏儒的力量作比较，有能打败该侏儒的精灵则选取当前满足条件的力量最小的精灵，否则就拿力量最小的精灵当炮灰去消耗对方，即田忌赛马的策略。

$\ \ \ \$ 现在的问题是，每一个位置也许都会有精灵从之前的位置走下来，因此很难找到一个合适的位置开始将精灵与侏儒进行匹配。（考场上没想到这点的我直接从 $1$ 开始跑然后卡死）

$\ \ \ \$ 因此，如果我们能找到一个位置使得没有精灵能从这个位置的逆时针方向走过来，那么它就可以作为起点。

$\ \ \ \$ 那么怎么才能找到这个位置呢？

$\ \ \ \$ 设：$d_i$ 表示 $[1,i]$ 位置之内总共安排多少精灵初始进入，即 $a$ 的桶的前缀和。

$\ \ \ \$ 可得当且仅当初始精灵数>座位数 ，即 $d_{j}-d_{i-1}>j-i+1$ 时，区间 $[i,j]$ 内的精灵会走到外面去。

$\ \ \ \$ 移项变为 $d_j-j>d_{i-1}-(i-1)$ 使不等式两边变为相似构造。并令 $P_i=d_i-i$ 。

$\ \ \ \$ 上式变形为 $P_j>P_{i-1}$ ，表示会有精灵经过 $j$ 到达 $j+1$ 。换句话说，如果有任意 $P_i < P_j$ , $j+1$ 就一定会被从 $j$ 来的精灵经过，就那么当我们找到一个 $j$ ，使得 $P_j$ 为 $\{P\}_{\min}$ 时，就一定没有精灵会经过 $j$ 到达 $j+1$ ， $j+1$ 就是我们要找的起点。

$\ \ \ \$ 找到起点后，我们就可以根据上面的思路贪心了，具体的实现和细节可以见代码。

$\mathcal{CODE}$

#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int arr[500005],s1[500005],s2[500005],d[500005];
set<int> S;
vector <int> s[500005];
set<int>::iterator it;
int solve(int sta)
{
	int ans=0,matched=0,now=sta;
	while(matched<n)
	{
		for(int i=0;i<s[now].size();i++) S.insert(s[now][i]);
		it=S.lower_bound(s1[now]);
		S.size();
		if(it==S.end()) S.erase(S.begin());
		else S.erase(it),ans++;
		matched++;
		now++;
		if(now>n) now-=n;
	}
	return ans;
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&arr[i]),d[arr[i]]++;
	for(int i=1;i<=n;i++) scanf("%d",&s1[i]);
	for(int i=1;i<=n;i++) scanf("%d",&s2[i]),s[arr[i]].push_back(s2[i]);
	int minn=1e9,min_index=-1e9;
	for(int i=1;i<=n;i++)
	{
		d[i]+=d[i-1];
		if(d[i]-i<minn) minn=d[i]-i,min_index=i;
	}
	int sta=min_index+1;
	if(sta>n) sta-=n;
	printf("%d",solve(sta));
	return 0;
}