hdu 5720(贪心+区间合并) Wool

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 347 Accepted Submission(s): 97

Problem Description

At dawn, Venus sets a second task for Psyche.

She is to cross a river and fetch golden wool from violent sheep who graze on the other side.

The sheep are wild and tameless, so Psyche keeps on throwing sticks to keep them away.

There are

. Help her calculate the number of valid sticks she can throw next time.

Input

The first line of input contains an integer

Output

For each test case, print the number of ways to throw a stick.

Sample Input

Sample Output

2
5
Hint

In the first example, $ 2, 3 $ are available.

In the second example, $ 6, 7, 8, 9, 10 $ are available.

Source

BestCoder 2nd Anniversary

题意:给出n,L,R，表示地上现在有n根树枝，你手里现有[L,R]长度的树枝各一根，要求选择一根树枝，不能与地上任意两根树枝构成三角形，问有多少种选法。

题解:假设当前的三角形三边分别为 a,b,c （a>=b）那么相对于a 能够扩展的范围就是 (a-b,a+b) 当 b尽量逼近 a 的时候扩展的范围最大,于是排序之后求出每个点管辖区间的范围,然后进行区间合并,一定要记得讨论区间边界。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 100005;
typedef long long LL;
const LL INF = 99999999999999;
LL a[N];
bool HASH[N];
struct Node{
    LL l,r;
}node[N];
int cmp(Node a,Node b){
    return a.l<b.l;
}
int main()
{
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        int n;
        LL l,r;
        scanf("%d%lld%lld",&n,&l,&r);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        sort(a+1,a+n+1);
        LL MIN = INF,MAX = -1;
        int id = 1;
        for(int i=2;i<=n;i++){
            LL k = a[i]-a[i-1]+1,t = a[i]+a[i-1]-1;
            if(k>=l&&t<=r){
                node[id].l = k;
                node[id++].r = t;
            }else if(k>=l&&t>=r){
                if(k>r) continue;
                if(k<=r){
                    node[id].l = k;
                    node[id++].r = r;
                }
            }else if(k<=l&&t<=r){
                if(t<l) continue;
                if(t>=l){
                    node[id].l = l;
                    node[id++].r = t;
                }
            }else if(k<=l&&t>=r){
                node[id].l = l;
                node[id++].r = r;
            }
        }
        if(id==1){
            printf("%lld
",r-l+1);
            continue;
        }
        LL cnt = 0;
        sort(node+1,node+id,cmp);
        LL start=node[1].l,pend = node[1].r;
        for(int i=2;i<id;i++){
            if(node[i].l>pend){
                cnt+=pend-start+1;
                start = node[i].l;
                pend = node[i].r;
            }else pend = max(node[i].r,pend);
        }
        cnt+=pend-start+1;
        printf("%lld
",r-l+1-cnt);
    }
    return 0;
}

hdu 5720(贪心+区间合并) Wool

相关推荐