几道Codeforces题目

本文从WordPress迁移而来, 查看全部WordPress迁移文章

题目链接:Case of Fugitive

题意 & 题解:

给了n个线段,坐标是Li, Ri的形式,这些线段不会重叠,而且是从左到右给出来的;给了m个桥,每条桥有长度。需要用这些桥,把两个相邻的线段连接起来,一个桥可以连接两个相邻的线段的条件如:

线段1: 1 4

线段2: 7 8

两线段的距离就是 7-4=3,桥的长度至少是3

两个线段的最大距离是 8-1 = 7, 桥的长度不能长过7

对桥的长度排序,先把短的桥用上;

对于每个相邻的线段,其实它有两个值,最小值,最大值;一个桥能连接两个相邻的线段一定是 最小值 <= 桥长度 <= 最大值; 对相邻线段的最小值排序 可以贪心,贪心的规则:对于当前这个桥,满足最小值 <= 桥长度 的条件下,选最大值最小的那一个; 做法:枚举桥(桥已经升序排序),扫描相邻线段,只要满足 最小值 <= 桥长度,都放进去一个小根堆里面,小根堆以相邻线段的最大值作为key。所以弹出来的元素,是最大值最小的

代码:

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>

using namespace std;

#define LL long long
#define mp make_pair
#define MAXN 200010

int n, m, ans[MAXN];
struct seg {
int id;
LL minl, maxl;
seg() {}
seg(int id_, LL minl_, LL maxl_):
id(id_), minl(minl_), maxl(maxl_) {}
bool operator> (const seg &x) const {
return maxl > x.maxl;
}
bool operator< (const seg &x) const {
return minl < x.minl;
}
}s[MAXN];
pair<LL, LL> bri[MAXN];

int main(){
while (scanf("%d%d", &n, &m) != EOF) {
memset(ans, -1, sizeof ans);
LL prel = -1, prer = -1, l, r;
for (int i = 0; i < n; i++, prel = l, prer = r) {
scanf("%lld%lld", &l, &r);
if (prel != -1) {
s[i-1] = seg(i-1, l - prer, r - prel);
}
}
sort(s, s + n - 1);
//for (int i = 0; i < n - 1; i++) {
// printf("%d %lld %lld\n", s[i].id, s[i].minl, s[i].maxl);
//}

for (int i = 0; i < m; bri[i].second = i, i++) {
scanf("%lld", &bri[i].first);
}
sort(bri, bri + m);

int sid = 0, ans_count = 0;
priority_queue<seg, vector<seg>, greater<seg> > pq;
for (int i = 0; i < m; i++) {
for (; sid < n - 1; sid++) {
if (s[sid].minl <= bri[i].first && bri[i].first <= s[sid].maxl) {
pq.push(s[sid]);
}
else break;
}
while (!pq.empty()) {
seg x = pq.top();
pq.pop();
if (x.minl <= bri[i].first && bri[i].first <= x.maxl) {
ans[x.id] = bri[i].second + 1;
ans_count++;
//printf("[%d] %lld, %lld\n", ans[x.id], x.minl, x.maxl);
break;
}
}
}
if (ans_count == n - 1) {
printf("Yes\n");
for (int i = 0; i < n - 1; i++)
printf("%d%c", ans[i], i == n - 2 ? '\n' : ' ');
}
else {
printf("No\n");
}

}
return 0;
}

题目链接:Boring Partition

题意 & 题解:

一个序列里面的元素,要么被划分到1部分,要么被划分到2部分(可以全部划分到1或2);对于两个元素,当他们在同一个部分时,f(ai, aj) = ai + aj,当他们在两个不同的部分时,f(ai, aj) = ai + aj + h,h是一个给定的值

要使得最大的 和 最小的 f(ai, aj) 它们的差值最小,要怎么划分这个序列,输出每个元素应该属于1还是属于2

虽然是div.1的B题不过貌似太简单了,对序列的元素降序排序后,选中间某个位置作为分界线,左边在1,右边在2即可;也就是左边的元素都大于右边的元素;

f(ai, aj)最大值一定出自1集合里面的最大两个数之和,或者1的最大值 + 2的最大值 + h

f(ai, aj)最小值一定出自2集合里面的最小两个数之和

所以我们只需要枚举中间的分界线即可

注意判断一下特殊情况即可,例如1集合只有1个元素,2集合只有1个元素,全部元素都在一个集合

代码:

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
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

#define LL long long
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair

#define MAXN 100010

int n, h;
pair<int, int> a[MAXN];

int main(){
while (scanf("%d%d", &n, &h) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%d", &a[i].first);
a[i].second = i;
}
if (n == 2) {
printf("0\n");
printf("1 1\n");
continue;
}
sort(a, a + n, greater<pair<int, int> >());
int mid = 0, max_delta = 0;
for (int i = 0; i < n; i++) {
if (i == 0) {
max_delta = a[0].first + a[1].first - (a[n-1].first + a[n-2].first);
mid = i;
}
else if (i == 1) {
int val_max = a[0].first + a[i].first + h;
int val_min = a[n-1].first + a[n-2].first;
if (val_max - val_min < max_delta) {
max_delta = val_max - val_min;
mid = i;
}
}
else if (i == n - 1) {
int val_max = max(a[0].first + a[1].first, a[0].first + a[n-1].first + h);
int val_min = min(a[n - 1].first + a[n - 2].first + h, a[n - 2].first + a[n - 3].first);
if (val_max - val_min < max_delta) {
max_delta = val_max - val_min;
mid = i;
}
}
else {
int val_max = max(a[0].first + a[1].first, a[0].first + a[i].first + h);
int val_min = a[n - 1].first + a[n - 2].first;
if (val_max - val_min < max_delta) {
max_delta = val_max - val_min;
mid = i;
}
}
}
for (int i = 0; i < n; i++) {
a[i].first = i < mid ? 1 : 2;
swap(a[i].first, a[i].second);
}
sort(a, a + n);
printf("%d\n", max_delta);
for (int i = 0; i < n; i++) {
printf("%d%c", a[i].second, i == n-1 ? '\n' : ' ');
}
}
return 0;
}