【题解】P3069 [USACO13JAN]牛的阵容Cow Lineup-C++

题目传送门

思路
这道题目可以通过尺取法来完成（我才不管什么必须用队列）
什么是尺取法呢？
顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。
之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案！
对于这道题，我们首先可以推出一个事实：

在任意一个符合条件的区间里，答案是区间内最多的那类牛的数量。

我们只需要从左到右扫描整个队列，找到每一个只含k+1种牛的区间（删除k种+保留的一种），取每个区间内数量最多牛的数量即可。

注意点：血统编号在0-1,000,000,000之间，需要离散化。

代码

 #include<bits/stdc++.h>

 using namespace std;

 map<int,int> mp;

 int a[],lsh,cnt,l=,r,c[],ans=-;

 int main()

 {

     int n,k;

     cin>>n>>k;

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

     {

         cin>>a[i];

         if(!mp[a[i]])mp[a[i]]=++lsh;

         a[i]=mp[a[i]];

     }

     while(r<=n)

     {

         r++;

         if(!c[a[r]])cnt++;

         c[a[r]]++;

         while(cnt==k+)

         {

             c[a[l]]--;

             if(!c[a[l]])cnt--;

             l++;

         }

         ans=max(c[a[r]],ans);

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

【题解】P3069 [USACO13JAN]牛的阵容Cow Lineup-C++

最新文章

热门文章