P9045 题解

lichenzhen · 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;
  }

  使用快读的参考代码