|
#2
书生牛犊2020-03-07 01:02
考虑到这里的时间是使用小于10^6的整数表示的，所以推荐下面这种算法。费空间，省时间，明思路。
 程序代码：int main(){ int A[1000001]={0};//初始化数组为0 读入每一组小H装车的时间an,bn 并且for(int i=an;i<=bn;i++)A[i]=1; //即把数组A视作时间轴，将小H装车的时间点全部标记起来。 类似地读入每一组小W装车的时间，并且for(int i=an;i<=bn;i++)A[i]+=1;//注意，这时候是要+1，方便标识出两人交谈的时间点 遍历A[]，所有2的节点都是两人碰面的时刻，这里要注意，只是碰面，不代表有交流的机会，得是连续的两个2才能算是一份交流时间，三个2算两份交流时间，以此类推。 汇总，print就行了 } [此贴子已经被作者于2020-3-7 01:11编辑过] |
只有本站会员才能查看附件，请 登录
n=int(input())
b=[]
c=[]
total_time=0
for i in range(n): #数据的录入
son=list(map(int,input().split()))
b.append(son)
son=[]
for i in range(n): #数据的录入
son=list(map(int,input().split()))
c.append(son)
son=[]
left=0 #控制第第一个人的数组
right=0 #控制第二个人的数组
while left<n and right<n:
if b[left][1]>c[right][0]: #如果b段的结束时间大于c时间段的开始时间
if b[left][1]>=c[right][1]: #判断这个结束时间是否大于c段的结束时间
if b[left][0]>=c[right][1]: #如果b段结束时间和开始时间都大于c段的结束时间就没有交流
right+=1
elif b[left][0]<=c[right][0]: #如果b段的开始时间小于c段的结束开始时间
total_time+=c[right][1]-c[right][0]
right+=1
else:
total_time+=c[right][1]-b[right][0]
right+=1
elif b[left][1]<c[right][1]:
if b[left][0]<=c[right][0]:
total_time+=b[left][1]-c[right][0]
left+=1
elif b[left][0]>c[right][0]:
total_time+=b[left][1]-b[left][0]
left+=1
elif b[left][1]<=c[right][0]:
left+=1
print(total_time)