HZNUOJ 1472 The nearest taller cow
5091 ワード
1472: The nearest taller cow
Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 151 Solved: 6 Scores: 94.48
Description
Farmer Zhao’s N cows (1 ≤ N ≤ 1,000,000) are lined up in a row. So each cow can see the nearest cow which is taller than it. You task is simple, given the height (0 < height ≤ 109) of each cow lined up in the row, to calculate the distance between each cow and its nearest taller cow (the nearest cow which is taller than him), if it is the tallest cow in the row, such distance is regarded as n. You should output the average distance.
Input
For each test case:
Line 1: One integers, N
Lines 2: N integers. The i-th integer is the height of the ith cow in the row.
Output
The average distance to their nearest taller cow, rounded up to 2 decimals.
Sample Input
7 7 6 5 8 6 4 10
Sample Output
2.43
HINT
You may suffer a precision problem. To ensure that you can output a correct answer on OJ(Online Judge), please write your output statements like it:
#define eps 1e-7
……
printf(“%.2f”,sum/n+eps);
——noted by CYP
Author
Source
湖南大学の2009校の試合
この問題は直接暴力がタイムアウトするので、このように最適化することができます.2つの方向を1回ずつ掃き、右に掃くことを例にとると、i頭目の牛を遍歴したとき、順路にその答えをメモすると、次の走査では、a[i]>=a[j]であれば、jは直接l[j]にジャンプすることができる.l[j]=kかつa[i]>=a[j]であれば、k-1~jもa[i]より小さいに違いないので、直接スキップすることができる.
ACコード
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define EPS 1e-8
const int MAX=1000000+100;
int a[MAX],l[MAX],r[MAX];
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1 ; i<=n ; ++i)
{
scanf("%d",&a[i]);
}
a[0]=a[n+1]=0x7fffffff;
l[1]=0;
for(int i=2 ; i<=n ; ++i)
{
int j=i-1;
while(a[i]>=a[j])
{
j=l[j];
}
l[i]=j;
}
r[n]=n+1;
for(int i=n-1 ; i>=1 ; --i)
{
int j=i+1;
while(a[i]>=a[j])
{
j=r[j];
}
r[i]=j;
}
long long sum=0;
for(int i=1 ; i<=n ; ++i)
{
if(r[i]==n+1 && l[i]==0)
{
sum+=n;
}
else if(r[i]==n+1)
{
sum+=i-l[i];
}
else if(l[i]==0)
{
sum+=r[i]-i;
}
else
{
sum+=min(r[i]-i,i-l[i]);
}
}
printf("%.2f
",(double)sum/n+EPS);
}
return 0;
}