BZOJ 1293: [SCOI2009]生日礼物【单调队列】

1293: [SCOI2009]生日礼物

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 2534  Solved: 1383

[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

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。

Source

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1293

分析:枚举起点找出每一种颜色在这个位置之后的第一个位置与这个位置距离的最大值,再找出每一个起点结果的最小值

首先我们把所有元素排一下序,然后枚举最小值,那么最大值是非严格单调上升的,就是一个珠子换成其后第一个的同颜色珠子时,将更新一下最大值,而最小珠子则刚好是其后第一个:

附图一张:【样例说明】

由图可知,选择3

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 inline int read()
 4 {
 5     int x=0,f=1;
 6     char ch=getchar();
 7     while(ch<'0'||ch>'9')
 8     {
 9         if(ch=='-')
10             f=-1;
11         ch=getchar();
12     }
13     while(ch>='0'&&ch<='9')
14     {
15         x=x*10+ch-'0';
16         ch=getchar();
17     }
18     return x*f;
19 }
20 #define inf 0x7f7f7f7f
21 int head[65];
22 const int N=1000010;
23 int next[N],v[N],a[N];
24 int n,k,ans=inf;
25 int cnt;
26 inline bool cal(int x)
27 {
28     int maxn=0;
29     for(int i=1;i<=k;i++)
30     {
31         while(v[head[i]]>x)
32         {
33             if(!next[head[i]])
34                 return false;
35             head[i]=next[head[i]];
36         }
37         if(v[head[i]]<=x)
38             maxn=max(maxn,x-v[head[i]]);//枚举起点找出每一种颜色在这个位置之后的第一个位置与这个位置距离的最大值
39     }
40     ans=min(ans,maxn);//找出每一个起点结果的最小值
41     return true;
42 }
43 int main()
44 {
45     n=read();
46     k=read();
47     for(int i=1;i<=k;i++)
48     {
49         int x=read();
50         for(int j=1;j<=x;j++)
51         {
52             int y=read();
53             v[++cnt]=y;
54             next[cnt]=head[i];
55             head[i]=cnt;
56             a[cnt]=y;
57         }
58     }
59     sort(a+1,a+1+cnt);
60     for(int i=cnt;i>0;i--)
61     {
62         if(a[i]!=a[i+1])
63         {
64             if(!cal(a[i]))
65                 break;
66         }
67     }
68     printf("%d\n",ans);
69     return 0;
70 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏耕耘实录

Linux三剑客之grep

版权声明:本文为耕耘实录原创文章,各大自媒体平台同步更新。欢迎转载,转载请注明出处,谢谢

19250
来自专栏salesforce零基础学习

salesforce 零基础学习(六十八)http callout test class写法

此篇可以参考: https://developer.salesforce.com/docs/atlas.en-us.apexcode.meta/apexcode...

31170
来自专栏龙首琴剑庐

Java基准测试利器OpenJDK-JMH

59790
来自专栏一“技”之长

一个移动开发者的Mock数据之路 原

    在前端开发中,很大一部分工作都是将后台数据获取到后展示在前端界面上。如果接口是现成的,这个过程还相对容易一些,但是如果接口的开发和前端开发是同时进行的,...

7710
来自专栏大闲人柴毛毛

张全蛋和李小花的故事——“代理模式”

举个例子: 假设张全蛋喜欢上了李小花,张全蛋准备给李小花送一些礼物,但张全蛋又非常害羞,因此买了礼物之后让王尼玛代送。王尼玛跑到李小花把礼物送给她之后就走了。 ...

397120
来自专栏calmound

D3DXCreateTextureFromFile

HRESULT D3DXCreateTextureFromFile( __in LPDIRECT3DDEVICE9 pDevice, _...

31750
来自专栏漫漫深度学习路

tensorflow:AToolDeveloperGuideToTFModelFIles

Tensorflow Model Files 最近闲来无聊,想深入理解一下tensorlfow,也不知从何下手,突然间发现了官方文档的Extend模块下还有这个...

37650
来自专栏xcywt

编译到底做了什么(***.c -> ***.o的过程)

 (第一次写博客,好激动的说.......) 我们知道,一个程序由源代码到可执行文件往往由这几步构成: 预处理(Prepressing)-> 编译(Compil...

20850
来自专栏数据结构与算法

09:LGTB 学分块

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB描述 LGTB 最近在学分块,但是他太菜了,分的块数量太多他就混乱...

35470
来自专栏云霄雨霁

数据结构----符号表

18800

扫码关注云+社区

领取腾讯云代金券