题目描述
狐进行了一次黑客马拉松大赛,全公司一共分为了N个组,每组一个房间排成一排开始比赛,比赛结束后没有公布成绩,但是每个组能够看到自己相邻的两个组里比自己成绩低的组的成绩,比赛结束之后要发奖金,以1w为单位,每个组都至少会发1w的奖金,另外,如果一个组发现自己的奖金没有高于比自己成绩低的组发的奖金,就会不满意,作为比赛的组织方,根据成绩计算出至少需要发多少奖金才能让所有的组满意。
输入描述:
每组数据先输入N,然后N行输入N个正整数,每个数表示每个组的比赛成绩。
输出描述:
输出至少需要多少w的奖金
输入
10
20
32
12
32
45
11
21
31
41
33
输出
20
思路:初始化奖金数组为1,从左往右遍历成绩数组,如果右边分数大于左边分数,则将右边分配的奖金加1(满足大于左边的需求),从右往左遍历成绩数组,如果左边分数大于右边分数,且左边分配的奖金小于(右边分配奖金+1),则更新左边分配的奖金(满足大于右边的需求)
<?php
function clear( &$moneys )
{
foreach ($moneys as &$money)
{
$money = 1;
}
}
function main( $num )
{
$i = 0;
$scores = array();
while ($i < $num)
{
$scores[] = intval(trim(fgets(STDIN)));
$i++;
}
$moneys = $scores;
clear($moneys);
//从左往右遍历,满足大于左边的限制
for ($i = 1; $i < $num; $i++ )
{
if ($scores[$i] > $scores[$i-1])
{
$moneys[$i] = $moneys[$i-1] + 1;
}
}
//从右往左遍历,满足大于右边的限制
for ($i = $num - 2; $i >= 0; $i--)
{
//左边分数大于右边分数
if ( ($scores[$i] > $scores[$i+1]) )
{
//左边分配奖金小于(右边分配奖金+1)进行更新
if ($moneys[$i] <= $moneys[$i+1])
{
$moneys[$i] = $moneys[$i+1] + 1;
}
}
}
return array_sum( $moneys );
}
while ($num = trim(fgets(STDIN)))
{
print main( $num )."
";
}