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

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

​​题目链接​​

题意：

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

思路：

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

#includeusing 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。