The 2018 ACM-ICPC Asia Qingdao Regional Contest I.Soldier Game
题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4066
题目大意
你需要把 $n$ 个士兵分成若干组，满足每组都有 $1$ 个或 $2$ 个士兵，且要保证士兵编号连续。求权值最大的组的权值减去权值最小的组的权值为多少。
题目分析
题目的意思为，用长度为 $1$ 和 $2$ 的线段不重叠覆盖序列，使得线段中最大值减去最小值最小。如果最小值能够固定，那么题目的做法可以类比最小生成树的做法，将所有线段按权值大小由小到大依次添加进去，维护是否可以完整覆盖。对于本体来说，可以先将所有 $n$ 个长度为 $1$ 的线段和 $n – 1$ 长度为 $2$ 的线段先提取出来，按照权值有效到大排序，通过枚举最小值，维护最小的最大值即可。在这个过程中，需要维护是否能完整覆盖。可以将为每个线段 $(l, r)$ 变成 $l$ 指向 $r + 1$ 的一条有向边，维护 $1$ 与 $n + 1$ 的连通性即可。由于枚举最小值时会有修改和删除操作，需要数据结构来维护。可以使用线段树维护区间的连通性，合并时考虑中间时直接连接还是跳一个连接。枚举所有可行的最小值，维护对应的最大值，对所有结果取最小值即为答案
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, t;
pair <long long, pair <int, int> > f[maxn];
long long a[maxn];
int b[maxn][2];
struct node {
int l, r;
int lc, rc;
bool v[2][2];
};
struct st {
node tree[maxn];
int root;
int tc;
int merge(node &ret, node x, node y){
if((x.v[0][0] and y.v[0][0] and b[x.r][0]) or (x.v[0][1] and y.v[0][0] and b[x.r - 1][1]) or (x.v[0][0] and y.v[1][0] and b[x.r][1])){
ret.v[0][0] = true;
}else{
ret.v[0][0] = false;
}
if((x.v[1][0] and y.v[0][0] and b[x.r][0]) or (x.v[1][1] and y.v[0][0] and b[x.r - 1][1]) or (x.v[1][0] and y.v[1][0] and b[x.r][1])){
ret.v[1][0] = true;
}else{
ret.v[1][0] = false;
}
if((x.v[0][0] and y.v[0][1] and b[x.r][0]) or (x.v[0][1] and y.v[0][1] and b[x.r - 1][1]) or (x.v[0][0] and y.v[1][1] and b[x.r][1])){
ret.v[0][1] = true;
}else{
ret.v[0][1] = false;
}
if((x.v[1][0] and y.v[0][1] and b[x.r][0]) or (x.v[1][1] and y.v[0][1] and b[x.r - 1][1]) or (x.v[1][0] and y.v[1][1] and b[x.r][1])){
ret.v[1][1] = true;
}else{
ret.v[1][1] = false;
}
if(x.l == x.r){
ret.v[1][0] = y.v[0][0];
if(y.r - y.l == 1){
ret.v[1][1] = true;
}
}
if(y.l == y.r){
ret.v[0][1] = x.v[0][0];
if(x.r - x.l == 1){
ret.v[1][1] = true;
}
}
return 0;
}
int update_tree(int pos, int l, int r){
int mid = (tree[pos].l + tree[pos].r) / 2;
if(tree[pos].l != tree[pos].r){
if(r <= mid){
update_tree(tree[pos].lc, l, r);
}else if(l <= mid and mid < r){
update_tree(tree[pos].lc, l, mid);
update_tree(tree[pos].rc, mid + 1, r);
}else{
update_tree(tree[pos].rc, l, r);
}
merge(tree[pos], tree[tree[pos].lc], tree[tree[pos].rc]);
}
return 0;
}
int init_tree(int l, int r){
int mid = (l + r) / 2;
int pos = ++tc;
tree[pos].l = l;
tree[pos].r = r;
memset(tree[pos].v, 0, sizeof(tree[pos].v));
if(l == r){
tree[pos].v[0][0] = true;
}else{
tree[pos].lc = init_tree(l, mid);
tree[pos].rc = init_tree(mid + 1, r);
}
return pos;
}
bool query(){
return tree[root].v[0][0];
}
int update(int x, int y){
update_tree(root, x, y);
return 0;
}
int init(){
tc = 0;
root = init_tree(1, n + 1);
return 0;
}
};
st tree;
int read(){
int x = 0;
int flag = 1;
char ch = getchar();
while('0' > ch or ch > '9'){
if(ch == '-'){
flag = -1;
}
ch = getchar();
}
while('0' <= ch and ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
x *= flag;
return x;
}
int solve(){
int i, j;
int x, y;
long long ans = 1e15;
int cnt = 0;
for(i=1;i<=n;i++){
f[i].first = a[i];
f[i].second.first = f[i].second.second = i;
}
for(i=1;i<n;i++){
f[n + i].first = a[i] + a[i + 1];
f[n + i].second.first = i;
f[n + i].second.second = i + 1;
}
sort(f + 1, f + 2 * n);
for(i=1;i<=n;i++){
b[i][0] = b[i][1] = false;
}
tree.init();
j = 0;
while(!tree.query()){
j++;
x = f[j].second.first;
y = f[j].second.second;
b[x][y - x] = true;
tree.update(x, y + 1);
}
for(i=1;i<2*n;i++){
ans = min(ans, f[j].first - f[i].first);
x = f[i].second.first;
y = f[i].second.second;
b[x][y - x] = false;
tree.update(x, y + 1);
while(!tree.query()){
j++;
if(j == 2 * n){
printf("%lld\n", ans);
return 0;
}
x = f[j].second.first;
y = f[j].second.second;
b[x][y - x] = true;
tree.update(x, y + 1);
}
}
return 0;
}
int main(){
int i, j;
t = read();
while(t--){
n = read();
for(i=1;i<=n;i++){
a[i] = read();
}
if(n == 1){
printf("0\n");
}else{
solve();
}
}
return 0;
}