P2205 画栅栏 Painting the Fence
题目描述
\(Farmer\) \(John\) 想出了一个给牛棚旁的长围墙涂色的好方法.(为了简单起见, 我们把围墙看做一维的数轴, 每一个单位长度代表一块栅栏) 他只是简单的把刷子蘸满颜料, 系在他最喜欢的奶牛 \(Bessie\) 上, 然后让 \(Bessie\) 来回地经过围墙, 自己则在一旁喝一杯冰镇的凉水.(......-_-|||) \(Bessie\) 经过的所有围墙都会被涂上一层颜料.\(Bessie\) 从围墙上的位置 \(0\) 出发, 并将会进行 \(N\) 次移动 \((1 <= N <= 100,000\)). 比如说,"\(10 L\)" 的意思就是 \(Bessie\) 向左移动了 \(10\) 个单位. 再比如说 "\(15 R\)" 的意思就是 \(Bessie\) 向右移动了 \(15\) 个单位. 给出一系列 \(Bessie\) 移动的清单.\(FJ\) 想知道有多少块栅栏涂上了至少 \(K\) 层涂料. 注意:\(Bessie\) 最多会移动到离原点 \(1,000,000,000\) 单位远的地方.
输入输出格式
输入格式:
第 1 行: 两个整数: \(N K\)
第 \(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
来源: http://www.bubuko.com/infodetail-2590208.html