自动搬运

查看原文

来自洛谷，原作者为

	lichenzhen 这个人已经AFO了

搬运于2025-08-24 22:44:53，当前版本为作者最后更新于2023-02-19 21:47:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

有 $n$ 瓶品牌不同的橙汁，其中第 $i$ 瓶的品牌是 $a_i$，求出使前 $k$ 瓶橙汁品牌不相同的最少操作的次数（只能交换两瓶相邻的橙汁）

题目解法

可以看出来，这是一道入门的贪心题目，但是还是有一定的思维难度的。还要用道桶思想。

首先，我们考虑一下什么时候是无解的。我们把橙汁出现的品牌的数量定义为 $d$，那么如果 $d<k$，此时无论如何都会有相同的品牌也就是无解。其他情况都是有解的。

之后考虑一下有解的时候如何做才能使操作次数最少，我们考虑想办法把没有出现过的品牌尽量往左边也就是前面移动，用一个桶来存储这个品牌是否出现，如何输入的是一个新的品牌，就把 $d+1$，之后就是计算将这个品牌移动需要的次数（也就是代价），次数就是 $i-(d+1)$，去括号可得 $i-d-1$，也就是用当前的位置减去已经出现的品牌再减去 $1$。

之后就是有两点值得注意的

• 要注意开long long，最终的操作次数会爆int（惨痛的教训，实测能得到 $86$ 分的高分）。
• 这道题目读入的数据量很大，最多可以读入 $10^5$ 个数据，使用cin速度比较慢（虽然也可以过），建议使用快读，提升的速度很大。截止到我发文前我使用快读的代码是最优解。

参考代码（不带快读）

#include<bits/stdc++.h>
using namespace std;
bool book[500001];//只需要两个数据就可以，开bool节省空间
long long ans;
int a,n,k,d;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		if(book[a]==0)
		{
			book[a]=1;
			ans+=i-d-1;
			d++;
		}
		if(d==k)//橙汁已经出现的品牌数已经满足了要求，直接输出代价并结束循环就可以了，后面的数据不用读了，节省时间。
		{
			cout<<ans;
			return 0;
		}
	}
	cout<<-1;
}

使用快读的参考代码