水题笔记_ [SCOI2009]生日礼物 [水题]

卡常让人迷失自我

传送至Luogu

卡常真的太爽了 而且容易上瘾…随手写了一个结果发现跑的挺快…然后就萌生了卡常的想法无法自拔…然而最后还是没卡到Rank1伤心

最后卡常了这个熊样…Rank1是怎么卡的啊

也许我再循环展开一下就卡过去了

Emmmmm…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 1)
#define MAXK (60 + 1)
#define LL long long
#define INF (0x7fffffff)
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, MAXN << 5, stdin), S == T) ? EOF : *S++)
char BB[MAXN * 5], *S = BB, *T = BB;
using namespace std;
struct node
{
int wz, bh;
}a[MAXN];
inline int cmp(const node& x, const node& y)
{ return x.wz < y.wz; }
inline int read()
{
register int c = 0, re = 0;
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
{
re = (re << 1) + (re << 3) + (c ^ '0');
c = getchar();
}
return re;
}
int main()
{
int cnt[MAXK];
memset(cnt, 0, sizeof(cnt));
// freopen("in.in", "r", stdin);
int n = read(), k = read();
// scanf("%d%d", &n, &k);
register int cnta = 0;
for (register int i = 1; i <= k; i++)
{
const int srt = read();
// scanf("%d", &srt);
for (register int j = 1; j <= srt; j++)
(a + (++cnta))->wz = read()/*scanf("%d", &a[++cnta].wz)*/, (a + cnta)->bh = i;
}
sort(a + 1, a + n + 1, cmp);
register int ans = INF, le = 1, ri = 0, dq = 0;
for (;;)
{
while (dq < k && ri < n)
{
++*(cnt + (a + (++ri))->bh);
if (*(cnt + (a + ri)->bh) == 1)
++dq;
}
if (dq != k)
break;
ans = min(ans, (a + ri)->wz - (a + le)->wz);
--*(cnt + (a + (le++))->bh);
if (!*(cnt + (a + le - 1)->bh))
--dq;
}
printf("%d", ans);
return 0;
}

By 沙茶Cansult