[BZOJ3535][Usaco2014 Open]Fair Photography

发布时间:2017-7-9 7:14:57编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[BZOJ3535][Usaco2014 Open]Fair Photography ",主要涉及到[BZOJ3535][Usaco2014 Open]Fair Photography 方面的内容,对于[BZOJ3535][Usaco2014 Open]Fair Photography 感兴趣的同学可以参考一下。

[BZOJ3535][Usaco2014 Open]Fair Photography

试题描述

FJ's N cows (1 <= N <= 100,000) are standing at various positions along a long one-dimensional fence. The ith cow is standing at position x_i (an integer in the range 0...1,000,000,000) and has breed b_i (an integer in the range 1..8). No two cows occupy the same position. FJ wants to take a photo of a contiguous interval of cows for the county fair, but we wants all of his breeds to be fairly represented in the photo. Therefore, he wants to ensure that, for whatever breeds are present in the photo, there is an equal number of each breed (for example, a photo with 27 each of breeds 1 and 3 is ok, a photo with 27 of breeds 1, 3, and 4 is ok, but 9 of breed 1 and 10 of breed 3 is not ok). Farmer John also wants at least K (K >= 2) breeds (out of the 8 total) to be represented in the photo. Help FJ take his fair photo by finding the maximum size of a photo that satisfies FJ's constraints. The size of a photo is the difference between the maximum and minimum positions of the cows in the photo. If there are no photos satisfying FJ's constraints, output -1 instead.

X的非负轴上有n头奶牛,每个奶牛有一个坐标xi和品种bi.
没有两头奶牛在同一个位置上.
选择一个区间[L,R],使得所有品种的奶牛数量, 在[L,R]中,要么为0,要么相等.且出现的品种数(注意是品种数而不是每个品种的个数丫> <.)至少为K.
区间长度定义为[L,R]中最右和最左的奶牛的差的绝对值.
求最长满足上述条件的区间长度.

输入

* Line 1: N and K separated by a space
* Lines 2..N+1: Each line contains a description of a cow as two integers separated by a space; x(i) and its breed id.

输出

* Line 1: A single integer indicating the maximum size of a fair photo. If no such photo exists, output -1. 

输入示例


上一篇:KRBTabControl(中文)Windows选项卡控件
下一篇:错误为Lc.exe已退出,代码为-1

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

最近更新

好贷网好贷款