传智杯 程序员节发橙子 思维

​​题目链接​​

题意：

现在给你n个数， 它们排成一个序列。现在要求分数高的同学获得的积分要比他相邻的同学获得的积分多，如果相邻两个同学获得的积分一样多，那么他们获得积分相同。问如何分配才能使所用积分最少。

思路：

我们初始化所有人的积分为1， 按照题意来，如果发现他前边的同学比他分数低，那么他的积分就比他前面的同学多1，相同就等于他前面的同学。
这是正序，然后再倒序来一次。
如果发现他后边的同学分数比他低，他的分数就比他后面的同学多1.注意，倒序时，一定要取最大值。这个多测样例就能发现。

#include<bits/stdc++.h>
using namespace std;
long long a[1000005], v[1000005];
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
v[i] = 1;
}
for(int i = 1;i <= n;i++)
{
if(a[i] > a[i - 1] && i != 1)
{
v[i] = v[i - 1] + 1;
}
else if(a[i] == a[i - 1])
{
v[i] = v[i - 1];
}
}
for(int i = n;i >= 1;i--)
{
if(a[i] > a[i + 1] && i != n)
{
v[i] = max(v[i + 1] + 1, v[i]);
}
else if(a[i] == a[i + 1])
{
v[i] = v[i + 1];
}
}
long long ans = 0;
for(int i = 1;i <= n;i++)
{
// cout << v[i] << " ";
ans += v[i];
}
//cout << endl;
cout << ans << endl;

return 0;
}