TOJ2640 The nearest taller cow-蒲公英云

TOJ2640 The nearest taller cow

小灰灰 2022-05-30 10:14 75阅读 0赞

描述

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. Your 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, if it is the tallest cow in the row, such distance is regarded as n. You should output the average distance.

输入

For each test case:
Line 1: One integers, N
Lines 2: N integers. The ith integer is the height of the ith cow in the row.

输出

The average distance to their nearest taller cow, rounded up to 2 decimals.

样例输入

7 6 5 8 6 4 10

样例输出

2.43

看n这么大吓我一跳，麻瓜的我依旧选择暴力好了…

用b,c数组可以优化一下，可以省一点时间，跳过一些区间。

最后计算sum的时候要考虑几种情况，因为一开始都设置为0了，

2 3 4 5 4 3 2 1 8 9

比如这组数据。如果不考虑b[i]!=0的话，5这个位置b[i]=0,c[i]=9，他会取4，而不是5。

#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<vector>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000100],b[1000100],c[1000100];
//a为原序列，b存左边比它大的最近的坐标，c存右边 
int main()
{
    int n,i,j,k,sum,max;
    while(scanf("%d",&n)!=EOF)
    {
        max=-1;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>max)
            max=a[i];
        }        
        memset(b,0,sizeof b);
        memset(c,0,sizeof c);
        b[1]=n;//最左边的数左边没有比它大的了
        c[n]=0;//最右边的数右边没有比它大的了 
        for(i=1;i<=n;i++)
        {
            for(j=i-1;j>0;)
            {
                if(a[j]>a[i])
                {
                    b[i]=j;
                    break;
                } 
                else
                {
                    if(b[i])
                    j=b[i];
                    else
                    j--;
                }
            }
            for(k=i+1;k<=n;)
            {
                if(a[k]>a[i])
                {
                    c[i]=k;
                    break;
                } 
                else
                {
                    if(c[i])
                    k=c[i];
                    else
                    k++;
                }
            }
        }
        //for(i=1;i<=n;i++)
        //printf("%d ",b[i]);
        //printf("\n");
        //for(i=1;i<=n;i++)
        //printf("%d ",c[i]);
        sum=0;
        for(i=1;i<=n;i++)
        {
            if(a[i]==max)
            sum+=n;
            else if(b[i]==0)
            sum+=fabs(c[i]-i);
            else if(c[i]==0)
            sum+=fabs(b[i]-i);
            else if(fabs(b[i]-i)>fabs(c[i]-i))
            sum+=fabs(c[i]-i);
            else
            sum+=fabs(b[i]-i);
            //printf("sum:%d\n",sum);
        }
        //printf("%d\n",sum); 
        double s;
        s=1.0*sum/n;
        printf("%.2lf\n",s);
    } 
}