[Luogu3069][USACO13JAN]牛的阵容Cow Lineup

摘要:
约翰觉得,如果一系列奶牛拥有相同的血统编号,那么这些奶牛看起来会更有力量。为了创建这样一个连续的分段,约翰最多可以选择k个血统的奶牛,并将它们全部赶出队列。请帮助约翰计算由具有相同血统数的牛组成的连续片段的最大长度?显然,最左边和合法的l不会随着r的增加而减少。

题目描述

Farmer John's N cows (1 <= N <= 100,000) are lined up in a row. Each cow is identified by an integer "breed ID" in the range 0...1,000,000,000; the breed ID of the ith cow in the lineup is B(i). Multiple cows can share the same breed ID.

FJ thinks that his line of cows will look much more impressive if there is a large contiguous block of cows that all have the same breed ID. In order to create such a block, FJ chooses up to K breed IDs and removes from his lineup all the cows having those IDs. Please help FJ figure out the length of the largest consecutive block of cows with the same breed ID that he can create by doing this.

农夫约翰的N(1 <= N <= 100,000)只奶牛排成了一队,每只牛都用编上了一个“血统编号”,该编号为范围0...1,000,000,000的整数。血统相同的奶牛有相同的编号,也就是可能有多头奶牛是相同的"血统编号"。

约翰觉得如果连续排列的一段奶牛有相同的血统编号的话,奶牛们看起来会更具有威猛。为了创造这样的连续段,约翰最多能选出k种血统的奶牛,并把他们全部从队列中赶走。

请帮助约翰计算这样做能得到的由相同血统编号的牛构成的连续段的长度最大是多少?

输入输出格式

输入格式:

* Line 1: Two space-separated integers: N and K.

* Lines 2..1+N: Line i+1 contains the breed ID B(i).

输出格式:

* Line 1: The largest size of a contiguous block of cows with

identical breed IDs that FJ can create.

输入输出样例

输入样例#1: 
9 1 
2 
7 
3 
7 
7 
3 
7 
5 
7 
输出样例#1: 
4 

说明

There are 9 cows in the lineup, with breed IDs 2, 7, 3, 7, 7, 3, 7, 5, 7. FJ would like to remove up to 1 breed ID from this lineup.

By removing all cows with breed ID 3, the lineup reduces to 2, 7, 7, 7, 7, 5, 7. In this new lineup, there is a contiguous block of 4 cows with the same breed ID (7).


我们发现,如果一个区间的颜色数量小于等于$K + 1$的话,那么这一段区间的最大答案就是出现次数最多的数。

显然最左的、合法的l随着r的增加而不减。

所以直接区间扫过去就行了。


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
#define reg register 
#define gc getchar
inline int read() {
    int res=0;char ch=gc();bool fu=0;
    while(!isdigit(ch)){if(ch=='-')fu=1;ch=gc();}
    while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48), ch=gc();
    return fu?-res:res;
}
map <int, int> mp;
int tot;
int n, k;
int a[100005];
int ans;
int cnt[100005];

int main()
{
    n = read(), k = read();
    for (reg int i = 1 ; i <= n ; i ++)
    {
        a[i] = read();
        if (!mp[a[i]]) mp[a[i]] = ++tot;
        a[i] = mp[a[i]];
    }
    int l = 1, r = 0;
    int num = 0;
    while(r <= n)
    {
        r ++;
        if (!cnt[a[r]]) num++;
        cnt[a[r]] ++;
        if (num >= k + 2)
        {
            while(l <= r and num >= k + 2) {
                if (cnt[a[l]] == 1) num--;
                cnt[a[l]]--;
                l++;
            }
        }
        ans = max(ans, cnt[a[r]]);
    }
    cout << ans << endl;
    return 0;
}

免责声明:文章转载自《[Luogu3069][USACO13JAN]牛的阵容Cow Lineup》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Android 圆角外边框朱砂掌健身养生功下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

索引节点(inode)爆满问题处理

后来,我用df-I检查/data分区的索引节点,发现它已满,这导致系统无法创建新的目录和文件。inode是用于存储这些数据的信息,包括文件大小、所有者、用户组、读写权限等。inode索引每个文件的信息,因此它具有inode的值。根据指令,操作系统可以通过inode值最快找到对应的文件。故障排除的原因是/data/cache目录中有大量小字节缓存文件,这些文件...

git:将两个请求合并为一个请求

Gitrebase ihEAD~2解释:此命令可以以文本形式显示您提交的两次请求。如果数字2被4替换,则您最近四次提交的信息将显示如下:1 pick56a06efchange1:删除一个空白行2 pickedbeab5change2:addlogonMainActivity34#Rebase23198ba..Edbeab5onto23198ba5#6#命令:...

codeforces 765 F Souvenirs 线段树+set

问题的含义:多个查询的间隔中两个数字之差的绝对值的最小值:可以根据查询的l对脱机查询进行排序,并且可以从r到l进行反向查询,并且间隔i+1到n的每次更新都可以确保此更新不会影响下一次和后续更新。因为当两个区间相互覆盖时,具有较小l的区间的值必须小于或等于另一个区间,因此可以绘制一个图来理解。...

css动画延迟好像有点怪

项目需要使用动画Css。自定义时,会发现设置动画延迟和动画持续时间的总时间不正确,这将导致动画丢失。例如,bounceInLeft动画从左侧出现,然后抖动。当初始动画延迟为0时,动画持续时间为1s,动画已完成,但如果设置该值,动画延迟为1s且动画持续时间是2s,则动画未完成。具体的动画是从左侧出现,然后在1s延迟后直接到达终点,但没有抖动。然后我用w3c写了...

Android:在任务列表隐藏最近打开的app

//schemas.android.com/apk/res/android“package=”com.li.test“android:versionName=”1.0“&gt:targetSdkVersion=”23“/&gt:allowBackup=”true“android:icon=”@mipmap/ic_launcher“androi...

微信小游戏流量主广告接入指南!

游戏通过审核发布上线,累计注册用户达到1000后,可以在管理后台开启流量主功能。广告接入广告类型有三种:激励式视频、插屏和BannerBanner广告接入需要注意:1.广告要显示全,不能放在屏幕外。我的游戏被以上原因拒绝了两次。我的banner广告是放在底部正中间,取最小宽度200。也就是尽量的小,不影响游戏操作。激励视频按钮一定要有视频广告相关的提示!...