题目大意
小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有$N$个，分为$K$种。简单的说，可以将彩带考虑为$x$轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。
小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。
题目分析
不难想到$O(n^2)$的枚举暴力。
正解可以记录每个颜色的前驱，枚举结束位置，然后枚举每一个颜色，将颜色移动到当前结束位置的前方，统计答案。
可以从后往前枚举结束位置同时删去无用链表元素优化时间。
代码
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005;
int cnt=0,ans=0x7fffffff/2,n,k,a[maxn],b[maxn],Next[maxn],Head[maxn];
int Cal(int x) {
int ans=0;
for(int i=1; i<=k; i++) {
while(b[Head[i]]>x) {
if(Next[Head[i]]==0)return 0x7fffffff/2;
Head[i]=Next[Head[i]];
}
if(b[Head[i]]<=x)ans=max(ans,x-b[Head[i]]);
}
return ans;
}
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=k; i++) {
int tmp=Get_Int();
while(tmp--) {
int x=Get_Int();
a[++cnt]=x;
b[cnt]=x;
Next[cnt]=Head[i];
Head[i]=cnt;
}
}
sort(a+1,a+n+1);
for(int i=n; i>=1; i--)ans=min(ans,Cal(a[i]));
printf("%d\n",ans);
return 0;
}
|
