admin 管理员组

文章数量: 887021

learning

题目描述

FJ 决定用他现有牛群的数据来制造一个自动分类机；它能猜测牛身上有没有斑点。不幸的是，FJ 没有很好的数据。对于他的N 头牛，他所知道的仅仅只是牛的重量，以及这头牛是否有斑点。所有的牛都有不同的重量。为了猜测一个新牛C 是否有斑点，FJ 先找到现有牛群中和新牛重量最接近的牛C’。如果这头牛有斑点，FJ 猜测新牛也有斑点；反之，新牛没有斑点。如果有两头牛和新牛重量差相等，如果有其中之一的牛有斑点，那么FJ 就猜测新牛也有斑点。FJ 用他的这种测试机在新进的一群牛身上。这批牛重量（连续整数）都在A 和B 之间（包含A;B）。请帮助他决定其中有多少牛会被分类为有斑点。
注意新的机器只会从FJ 现有的牛群中比较数据，不会在他任何新牛中比较。还有注意，由于A 和B 都可能很大，你的程序如果从A B 一个一个的循环很可能跑不快。

输入

第一行三个数N; A;B，
接下一行N 行
每行要么是‘S W’，表示有一头有斑点的牛重量是W
要么是‘NS W’，表示有一头没有斑点的牛重量是W
数据保证任意两头牛的重量都不相等

输出

要你输出有多少牛会被看成是有斑点

样例输入

3 1 10
S 10
NS 4
S 1

样例输出

6

Explanation

1, 2, 7, 8, 9, and 10 有斑点

数据范围限制

• 对于40% 的数据，1 <= A <= B <= 10^7。
• 对于100% 的数据，N<= 5 * 10^4，1 <= A <= B <= 10^9，1 <= W <= 10^9。

思路：

快拍+两边MID判断

淼淼淼淼………………………………

代码：

vars,o,p,op,l,u,r,d,q:array[0..50000,1..2] of int64;f:array[1..50000] of char;w1:array[1..50000] of int64;c,oc:char;n,a,b,w,ow,i,j,k,x,y,z,ls:longint;ans:qword;
procedure qs(l,r:longint);
vari,j,mid:int64;ls1:char;ls2:int64;
begini:=l;j:=r;mid:=w1[(l+r) div 2];while i<=j dobeginwhile w1[j]>mid dobeginj:=j-1;end;while w1[i]<mid dobegini:=i+1;end;if i<=j thenbeginls1:=f[i];ls2:=w1[i];f[i]:=f[j];w1[i]:=w1[j];f[j]:=ls1;w1[j]:=ls2;i:=i+1;j:=j-1;end;end;if i<r then qs(i,r);if j>l then qs(l,j);
end;
procedure jia(l,r:longint);
beginif (l<=a)and(b<=r) thenbeginans:=ans+b-a+1;endelsebeginif (l>=a)and(r<=b) thenbeginans:=ans+r-l+1;endelsebeginif (r<a)or(l>b) thenexit;if (l<=a)and(r<=b) thenbeginans:=ans+r-a+1;endelsebeginans:=ans+b-l+1;end;end;end;
end;
beginassign(input,'learning.in');reset(input);assign(output,'learning.out');rewrite(output);readln(n,a,b);for i:=1 to n dobeginread(c);if c='N' thenbeginreadln(c,w);c:='N';f[i]:=c;w1[i]:=w;endelsebeginreadln(w);f[i]:=c;w1[i]:=w;end;end;qs(1,n);oc:=f[1];ow:=w1[1];if (f[1]='S')and(a<=w1[1]) thenbeginjia(a,w1[1]);end;for i:=2 to n dobeginc:=f[i];if c='N' thenbeginw:=w1[i];if oc='S' thenbegins[0,1]:=s[0,1]+1;s[s[0,1],1]:=ow+1;s[s[0,1],2]:=ow+(abs(w-ow)+1) div 2 + (abs(w-ow)+1) mod 2 -1;jia(s[s[0,1],1],s[s[0,1],2]);end;endelsebeginw:=w1[i];if oc='N' thenbegins[0,1]:=s[0,1]+1;s[s[0,1],1]:=ow+(abs(w-ow)+1) div 2;s[s[0,1],2]:=w;jia(s[s[0,1],1],s[s[0,1],2]);endelsebegins[0,1]:=s[0,1]+1;s[s[0,1],1]:=ow+1;s[s[0,1],2]:=w;jia(s[s[0,1],1],s[s[0,1],2]);end;end;oc:=c;ow:=w;end;if (f[n]='S')and(b>w1[n]) thenbeginjia(n+1,b);end;writeln(ans);
end.

本文标签： learning

版权声明：本文标题：learning 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687458804h104861.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。