 2018-11-14 10:43

# 一个有关天气预报的算法C语言问题

Problem Description
"Man, this year has the worst weather ever!", David said as he sat crouched in the small cave where we had sought shelter from yet another sudden rainstorm.
"Nuh-uh!", Diana immediately replied in her traditional know-it-all manner.
"Is too!", David countered cunningly. Terrific. Not only were we stuck in this cave, now we would have to listen to those two nagging for at least an hour. It was time to cut this discussion short.
"Big nuh-uh. In fact, 93 years ago it had already rained five times as much by this time of year."
"Duh", David capitulated, "so it's the worst weather in 93 years then."
"Nuh-uh, this is actually the worst weather in 23 years.", Diana again broke in.
"Yeah, well, whatever", David sighed, "Who cares anyway?".
Well, dear contestants, you care, don't you?
Your task is to, given information about the amount of rain during different years in the history of the universe, and a series of statements in the form "Year X had the most rain since year Y", determine whether these are true, might be true, or are false. We say that such a statement is true if:

The amount of rain during these two years and all years between them is known.

It rained at most as much during year X as it did during year Y.

For every year Z satisfying Y < Z < X, the amount of rain during year Z was less than the amount of rain during year X.

We say that such a statement might be true if there is an assignment of amounts of rain to years for which there is no information, such that the statement becomes true. We say that the statement is false otherwise.

Input
The input will consist of several test cases, each consisting of two parts.
The first part begins with an integer 1 <= n <= 50000, indicating the number of different years for which there is information. Next follow n lines. The ith of these contains two integers -109 <= yi <= 109 and 1 <= ri <= 109 indicating that there was ri millilitres of rain during year yi (note that the amount of rain during a year can be any nonnegative integer, the limitation on ri is just a limitation on the input). You may assume that yi < yi+1 for 1 <= i < n.
The second part of a test case starts with an integer 1 <= m <= 10000, indicating the number of queries to process. The following m lines each contain two integers -109 <= Y < X <= 109 indicating two years.
There is a blank line between test cases. The input is terminated by a case where n = 0 and m = 0. This case should not be processed.
Technical note: Due to the size of the input, the use of cin/cout in C++ might be too slow in this problem. Use scanf/printf instead. In Java, make sure that both input and output is buffered.

Output
There should be m lines of output for each test case, corresponding to the m queries. Queries should be answered with "true" if the statement is true, "maybe" if the statement might be true, and "false" if the statement is false.
Separate the output of two different test cases by a blank line.

Sample Input
4
2002 4920
2003 5901
2004 2832
2005 3890
2
2002 2005
2003 2005

3
1985 5782
1995 3048
2005 4890
2
1985 2005
2005 2015

0
0

Sample Output
false
true

maybe
maybe

• 写回答
• 关注问题
• 收藏
• 邀请回答

#### 2条回答默认 最新

• fenghua2010nb 2018-11-15 06:06

#include
#include
using namespace std;
#define maxn 50010

int n, m;
struct point
{
int year, r;
}pt[maxn];

struct Tree
{
int Max;
int l, r;
}T[maxn*4];

int MMax(int a, int b)
{
return a > b ? a : b;
}

void Build(int p, int l, int r)
{
T[p].l = l;
T[p].r = r;
if(l == r)
{
T[p].Max = pt[l].r;
return ;
}
int mid = (l + r) >> 1;
Build(p< Build(p T[p].Max = max(T[p }
int Query(int p, int l, int r)
{
if(r T[p].r)
return 0;
if(l <= T[p].l && T[p].r <= r)
return T[p].Max;
return max(Query(p<<1, l, r), Query(p<<1|1, l, r));
}

int Binary(int val, int l, int r)
{
int ans = 0;
while(l <= r) {
int m = (l + r) >> 1;
if(pt[m].year <= val)
{
l = m + 1;
ans = m;
}else
r = m - 1;
}
return ans;
}

// 连续的块种类
int Coces[maxn];

int main()
{
int i;
int t = 0;
while(scanf("%d", &n) != EOF)
{

``````    if(t++ && n)
{
puts("");
}
for(i = 1; i <= n; i++)
{
scanf("%d %d", &pt[i].year, &pt[i].r);
if(i == 1)
{
Coces[i] = 1;
}
else
{
if(pt[i].year - pt[i-1].year == 1)
Coces[i] = Coces[i-1];
else
Coces[i] = Coces[i-1] + 1;
}
}
if(n)
Build(1, 1, n);
scanf("%d", &m);
int bufM = m;
while(bufM--)
{
int Y, X;
int ans; // 0 true 1 maybe 2 false
scanf("%d %d", &Y, &X);
int fY = Binary(Y, 1, n);
int fX = Binary(X, 1, n);
if(pt[fY].year == Y && pt[fX].year == X)
{
// 都能找到数据中有的年份
int Yr = Query(1, fY, fY);
int Zr = Query(1, fY+1, fX-1);
// Y+1 == X 的情况在这里Zr返回的是0，所以肯定满足
int Xr = Query(1, fX, fX);
if(Coces[fY] == Coces[fX])
{
// 之间的年份全部连续
if(Yr >= Xr && Zr < Xr)
{
ans = 0;
}
else
ans = 2;
}
else
{
// 之间的年份不连续
if(Yr >= Xr && Zr < Xr)
{
ans = 1;
}
else
ans = 2;
}
}
else if(pt[fX].year == X)
{
// X这一年数据中有
if(Y + 1 == X)
{
// 当前两年连续
ans = 1;
}else
{
int Zr = Query(1, fY+1, fX-1);
int Xr = Query(1, fX, fX);
if(Zr < Xr)
ans = 1;
else
ans = 2;
}
}
else if(pt[fY].year == Y)
{
int Yr = Query(1, fY, fY);
int Zr = Query(1, fY+1, fX);
if(Yr > Zr)
{
ans = 1;
}else
ans = 2;
}
else
{
// X 和 Y 都没有出现，肯定是maybe
ans = 1;
}

if(!ans)
puts("true");
else if(ans == 1)
puts("maybe");
else
puts("false");
}
if(!n && !m)
{
break;
}
}
return 0;
``````

}

打赏 评论