前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1293: [SCOI2009]生日礼物

1293: [SCOI2009]生日礼物

作者头像
HansBug
发布2018-04-10 16:21:39
8400
发布2018-04-10 16:21:39
举报
文章被收录于专栏:HansBug's Lab

1293: [SCOI2009]生日礼物

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 1096  Solved: 584

[Submit][Status]

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

 题解:这个嘛,终于没有脑抽啦(phile:好评如潮 HansBug:么么哒)。。。思路也比较简单,就是直接通过那个啥的各个柱子(HansBug:啊呸,珠子 phile:你啊一看就是被Aruba多了。。。 HansBug:TT这都被你发现了)的坐标从小到大排个序,然后先从1开始找一段最短的可满足题意的子段,记录下长度,然后把这个子段第一个位置的各个珠子全部扔掉,再在结尾处往下扩充,每次都尽可能少的扩充但是要满足扩充后能包含M种珠子,然后每次记录下当前段的长度,这样子滚过去一边就可以啦,理论复杂度为O(nlogn+n)(PS:1.提醒一下,注意彩珠位置可以是0,所以在排序的数组中建议存储时+1,反正不影响结果,而且后续处理时少不少麻烦 2.这题居然3928ms我也是醉了,估计这个序列比较有序,所以快排比较逗比么么哒)

 1 var

代码语言:javascript
复制
2    i,j,k,l,m,n,ll:longint;
 3    a,b,c:array[0..1000500] of longint;
 4 procedure swap(var x,y:longint);
 5           var z:longint;
 6           begin
 7                z:=x;x:=y;y:=z;
 8           end;
 9 procedure sort(l,r:longint);
10           var i,j,x,y:longint;
11           begin
12                i:=l;j:=r;x:=a[(i+j) div 2];
13                repeat
14                      while a[i]<x do inc(i);
15                      while a[j]>x do dec(j);
16                      if i<=j then
17                         begin
18                              swap(a[i],a[j]);
19                              swap(b[i],b[j]);
20                              inc(i);dec(j);
21                         end;
22                until i>j;
23                if i<r then sort(i,r);
24                if l<j then sort(l,j);
25           end;
26 begin
27      readln(n,m);
28      fillchar(a,sizeof(a),0);
29      fillchar(b,sizeof(b),0);
30      for i:=1 to m do
31          begin
32               read(l);
33               for j:=1 to l do
34                   begin
35                        read(k);
36                        inc(a[0]);a[a[0]]:=k+1;
37                        b[a[0]]:=i;
38                   end;
39               readln;
40          end;
41      a[0]:=0;l:=0;
42      sort(1,n);
43      fillchar(c,sizeof(c),0);
44      i:=1;
45      j:=1;
46      while (l<m) and (j<=n) do
47            begin
48                 k:=j;
49                 while a[j]=a[k] do
50                       begin
51                            inc(c[b[j]]);
52                            if c[b[j]]=1 then inc(l);
53                            inc(j);
54                       end;
55            end;
56      if j>n then halt;
57      ll:=a[j-1]-a[i];
58      while j<=n do
59            begin
60                 k:=i;
61                 while a[i]=a[k] do
62                       begin
63                            dec(c[b[i]]);
64                            if c[b[i]]=0 then dec(l);
65                            inc(i);
66                       end;
67                 while (l<m) and (j<=n) do
68                       begin
69                            k:=j;
70                            while (l<m) and (a[j]=a[k]) do
71                                  begin
72                                       inc(c[b[j]]);
73                                       if c[b[j]]=1 then inc(l);
74                                       inc(j);
75                                  end;
76                       end;
77                 if l<m then break;
78                 if (a[j-1]-a[i])<ll then ll:=a[j-1]-a[i];
79            end;
80      writeln(ll);
81 end.
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2014-12-29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1293: [SCOI2009]生日礼物
  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • HINT
  • Source
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档