cf1119d Frets On Fire 前缀和+二分

题目:http://codeforces.com/problemset/problem/1119/D

题意:给一个数n,给出n个数组的第一个数(a[0]=m,a[1]=m+1,a[2]=m+2,...,a[n]=m+n),给定q个查询,每个查询问所有数组的[l,r]区间内总共出现了多少个不同的数。

思路:答案与给出查询的区间无关,只与区间长度有关。

 

两数组不重复的数与数组第一个数的差、区间长度有关。两数组内不重复的数为min(两数组a[0]之差,区间长度)。

因此对数组第一个数进行sort,之和求出数组第一位之差delta[],再按照升序排序,小于区间长度的都取delta[],大于区间长度的都取len。

然后对delta求一下前缀和sum,查找的时候对delta进行二分。

cf1119d Frets On Fire 前缀和+二分

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
long long s[maxn]={0},delta[maxn]={0},sum[maxn]={0}; 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%lld",&s[i]);
    sort(s,s+n);
    for(int i=0;i<n-1;i++)delta[i]=s[i+1]-s[i];
    sort(delta,delta+n-1);
    for(int i=0;i<n;i++)
    {
        sum[i+1]=sum[i]+delta[i];
    }
    
    int q;
    scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        long long l,r,len,ans=0;
        scanf("%lld%lld",&l,&r);
        len=r-l+1;
        int p=upper_bound(delta,delta+n-1,len)-delta;
        ans=sum[p]+len*(n-p);
        if(i!=q-1)printf("%lld ",ans);
        else printf("%lld\n",ans);
    }
    return 0; 
} 

 

上一篇:【网易官方】极客战记(codecombat)攻略-森林-荆棘农场


下一篇:kuangbin专题 专题一 简单搜索 Fire! UVA - 11624