NC24110. [USACO 2015 Dec B]Speeding Ticket
描述
The road is exactly 100 miles long, and Bessie drives the entire length of the road before ultimately being pulled over by a police officer, who gives Bessie a ticket for exceeding the speed limit, for having an expired license, and for operating a motor vehicle while being a cow. While Bessie concedes that the last two tickets are probably valid, she questions whether the police officer was correct in issuing the speeding ticket, and she wants to determine for herself if she has indeed driven faster than the speed limit for part of her journey.
The road is divided into NN segments, each described by a positive integer length in miles, as well as an integer speed limit in the range 1…1001…100 miles per hour. As the road is 100 miles long, the lengths of all NN segments add up to 100. For example, the road might start with a segment of length 45 miles, with speed limit 70, and then it might end with a segment of length 55 miles, with speed limit 60.
Bessie's journey can also be described by a series of segments, MM of them. During each segment, she travels for a certain positive integer number of miles, at a certain integer speed. For example, she might begin by traveling 50 miles at a speed of 65, then another 50 miles at a speed of 55. The lengths of all MM segments add to 100 total miles. Farmer John's tractor can drive 100 miles per hour at its fastest.
Given the information above, please determine the maximum amount over the speed limit that Bessie travels during any part of her journey.
输入描述
The first line of the input contains NN and MM, separated by a space.
The next NN lines each contain two integers describing a road segment, giving its length and speed limit.
The next MM lines each contain two integers describing a segment in Bessie's journey, giving the length and also the speed at which Bessie was driving.
输出描述
Please output a single line containing the maximum amount over the speed limit Bessie drove during any part of her journey. If she never exceeds the speed limit, please output 0.
示例1
输入:
3 3 40 75 50 35 10 45 40 76 20 30 40 40
输出:
5
说明:
In this example, the road contains three segments (40 miles at 75 miles per hour, followed by 50 miles at 35 miles per hour, then 10 miles at 45 miles per hour). Bessie drives for three segments (40 miles at 76 miles per hour, 20 miles at 30 miles per hour, and 40 miles at 40 miles per hour). During her first segment, she is slightly over the speed limit, but her last segment is the worst infraction, during part of which she is 5 miles per hour over the speed limit. The correct answer is therefore 5.C(clang11) 解法, 执行用时: 1ms, 内存消耗: 376K, 提交时间: 2020-11-07 10:40:01
#include<stdio.h>
int a[1000],b[1000];
int m,n;
int main()
{
scanf("%d%d",&m,&n);
int i,j,k,s;
j=0;
for(i=0;i<m;i++)
{
scanf("%d%d",&k,&s);
while(k--)
a[++j]=s;
}
j=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&k,&s);
while(k--)
b[++j]=s;
}
int max=0;
for(i=1;i<=100;i++)
if(max<b[i]-a[i])
max=b[i]-a[i];
printf("%d",max);
return 0;
}
C++(clang++11) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2020-11-07 11:11:07
#include<iostream>
#include<cstdio>
using namespace std;
int a[110],b[110];
int main()
{
int n,m;
cin>>n>>m;
int x=0,y,k;
for(int i=1;i<=n;i++)
{
cin>>k>>y;
x+=k;
for(int j=x-k+1;j<=x;j++) a[j]=y;
}
x=0;
for(int i=1;i<=m;i++)
{
cin>>k>>y;
x+=k;
for(int j=x-k+1;j<=x;j++) b[j]=y;
}
int ans=0;
for(int i=1;i<=100;i++)
ans=max(b[i]-a[i],ans);
cout<<ans<<endl;
return 0;
}