MYF

HDU 5720 Wool

Posted on | In | | Visitors

题目链接

HDU 5720

解题方法：区间处理

题目分析

题目大意

中文题面

解析

赛后按照官方解析写了一遍，按照闭区间计算，然后算出总长度R-L+1然后删点。有一个比较坑的地方花了我很长时间，在处理线段seg的时候应当维护可延伸至的最大边界right，否则可能会重复删点。

1
2
3
4
5
6
7
8
9
//正确代码
   ll ans = R-L+1,right=-1;
   for (int i=1; i<cnt; i++) {
       if (seg[i].l>right)
           ans -= seg[i].r-seg[i].l+1;
       else if (seg[i].r>right)
           ans -= seg[i].r-right;
       right=max(right, seg[i].r);
   }
1
2
3
4
5
6
7
8
//错误代码
	ll ans = R-L+1;
   for (int i=1; i<cnt; i++) {
       if (seg[i].l>seg[i-1].r)
           ans -= seg[i].r-seg[i].l+1;
       else if (seg[i].r>seg[i-1].r)
           ans -= seg[i].r-seg[i].l;	//可能处理的不是右端点最大的线段
   }

官方解析：

考虑三角形三条边$ a,b,c $ $ (a \ge b) $的关系$ a - b < c, a + b > c $，即$ c \in (a-b,a+b) $。 令加入的边为$ c $，枚举所有边作为$ a $的情况。对于所有可行的$ b $，显然与$ a $相差最小的可以让$ (a-b,a+b) $覆盖范围最大，所以可以贪心地选择不大于$ a $的最大的$ b $。 于是我们可以先将边按长度排序，然后$ ai $和$ a{i + 1} $建一条线段。线段并是不合法的部分。 将所有线段按左端点排序，按序扫描一遍，过程中统计答案即可。 时间复杂度$ O(Tn\ \log n) $。

代码

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
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int mod=998244353;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
ll a[maxn],L,R;
int t,n;
struct Segment{
    ll l,r;
    bool operator<(Segment x)const{
        return l!=x.l?(l<x.l):(r<x.r);
    }
}seg[maxn];
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%d%lld%lld",&n,&L,&R);
        for (int i=0; i<n; i++)
            scanf("%lld",&a[i]);
        sort(a, a+n);
        int cnt=1;
        for (int i=1; i<n; i++) {
            seg[cnt].l = a[i]-a[i-1]+1;
            seg[cnt].r = a[i]+a[i-1]-1;
            if (seg[cnt].l>R||seg[cnt].r<L)
                continue;
            seg[cnt].l=max(seg[cnt].l, L);
            seg[cnt].r=min(seg[cnt].r, R);
            cnt++;
        }
        sort(seg+1, seg+cnt);
        ll ans = R-L+1,right=-1;
        for (int i=1; i<cnt; i++) {
            if (seg[i].l>right)
                ans -= seg[i].r-seg[i].l+1;
            else if (seg[i].r>right)
                ans -= seg[i].r-right;
            right=max(right, seg[i].r);
        }
        cout<<ans<<endl;
    }
    return 0;
}