P2205 题目有感

ButterflyDew · 2018-05-04 16:48:19 · 个人记录

P2205 画栅栏Painting the Fence

题目描述

第2...N+1 行： 每一行都描述了Bessie的一次移动。 （比如说 “15 L"）

输出格式：

一个整数：被至少涂上K层涂料的栅栏数

不知道为什么，一开始死活想不到咋离散。。

其实只需要取出现过的区间就行了。

多次修改区间一次询问，差分会比较快，O(1)修改,O(n)询问了。

code：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=200010;
int n,k;
int a[N];
char c;
struct node
{
    int d,loc;
    friend bool operator <(node n1,node n2)
    {
        return n1.loc<n2.loc;
    }
}t[N],f[N];
int main()
{
    scanf("%d%d",&n,&k);
    int to,now=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %c",&to,&c);
        if(c=='R')
        {
            now+=to,a[i]=now;
            t[++cnt].loc=a[i-1];
            t[cnt].d=1;
            t[++cnt].loc=a[i];
            t[cnt].d=-1;
        }
        else
        {
            now-=to,a[i]=now;
            t[++cnt].loc=a[i];
            t[cnt].d=1;
            t[++cnt].loc=a[i-1];
            t[cnt].d=-1;
        }

    }
    sort(t+1,t+1+cnt);
    int cnt0=0;
    for(int i=1;i<=cnt;i++)
    {
        if(f[cnt0].loc==t[i].loc)
            f[cnt0].d+=t[i].d;
        else
            f[++cnt0].d=f[cnt0-1].d+t[i].d,f[cnt0].loc=t[i].loc;
    }
    int ans=0;
    for(int i=1;i<cnt0;i++)
        if(f[i].d>=k)
            ans+=f[i+1].loc-f[i].loc;
    printf("%d\n",ans);
    return 0;
}

2018.5.4