[SCOI2009]生日礼物(尺取法)
2024-08-29 12:13:41
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2201 Solved: 1186
[Submit][Status][Discuss]
Description
小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。 小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希望这段彩带尽可能短,你能帮助小西计算这个最短的长度么?彩带的长度即为彩带开始位置到结束位置的位置差。
Input
第一行包含两个整数N, K,分别表示彩珠的总数以及种类数。接下来K行,每行第一个数为Ti,表示第i种彩珠的数目。接下来按升序给出Ti个非负整数,为这Ti个彩珠分别出现的位置。
Output
应包含一行,为最短彩带长度。
Sample Input
6 3
1 5
2 1 7
3 1 3 8
1 5
2 1 7
3 1 3 8
Sample Output
3
HINT
有多种方案可选,其中比较短的是1~5和5~8。后者长度为3最短。
【数据规模】
对于50%的数据, N≤10000;
对于80%的数据, N≤800000;
对于100%的数据,1≤N≤1000000,1≤K≤60,0≤彩珠位置<2^31。
坑点在于,我往二分里使劲钻
尺取法:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; #define MAXN 1000005
#define INF 2147483647 struct Node
{
int pos;
int k;
bool operator < (const Node & b)const {return pos<b.pos;}
}zhu[MAXN]; int n,k; int kind[]; int main()
{
while (scanf("%d%d",&n,&k)!=EOF)
{
int num=;
for (int i=;i<k;i++)
{
int x;
scanf("%d",&x);
while (x--)
{
int v;
scanf("%d",&v);
zhu[num++]=(Node){v,i};
}
}
sort(zhu,zhu+num); memset(kind,,sizeof(kind));
int ans=INF;
int l=,r=;
int k_n=;
while()
{
while (r<n&&k_n<k)
if (!kind[zhu[r++].k]++) k_n++;
while (k_n==k&&l<r)
{
if (zhu[r-].pos-zhu[l].pos<ans) ans = zhu[r-].pos-zhu[l].pos;
if (!--kind[zhu[l++].k]) k_n--;
}
if (r>=n) break;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- sqlServer去除字符串空格
- TFS Build Definition And Auto Deploy
- IOS开发之—— 上传头像的使用
- poj2193
- POJ 1149 PIGS 【网络流】
- C++ inline(内联什么时候使用)
- APP 上传之后出现";invalid binary"; 问题解决汇总
- C#几种截取字符串的方法小结,需要的朋友可以参考一下
- java 获取特定天数的时间戳
- 一.redis 环境搭建
- 电池和Adapter切换电路改进实验(转)
- python爬虫入门-开发环境与小例子
- 文件A包含文件B,找出A不包含B的那部分
- uni-app—从安装到卸载
- poj3104 Drying(二分最大化最小值 好题)
- C++中常用的std标准容器
- vue框架之自定义组件中使用v-model
- 当Ruby的model名字出错时,在现实view时显示错误的提示
- tomcat源码阅读之载入器(Loader)
- java url生成二维码保存到本地
热门文章
- Git历险记(二)——Git的安装和配置
- org.apache.hadoop.ipc.RemoteException: User: root is not allowed to impersonate root
- 分布式服务自增长唯一ID小结
- Apache环境下搭建KodExplorer网盘
- [PWA] Disable Text Selection and Touch Callouts in a PWA on iOS
- 输出C语言中 变量的类型
- Android学习(十九)Dialog对话框
- Nmon命令行:Linux系统性能的监测利器
- 【BIEE】06_UNION /UNION ALL集合中分类汇总求和占比字段特殊处理
- PIVOT 和 UPIVOT 的使用(行转列)