NC25189. 杨主席发糖
描述
19 年校赛的结果已经出炉，为了对大家的积极参与表示感谢，杨主席准备拿出他的工资给大家发福利。
所有参赛选手排成一排，每位同学都对于有一个量化的得分（当然，得分越高越好）。杨主席已事先知道选手们的排队顺序以及个人的得分，他将一个一个给大家发糖。
杨主席是个有原则的男人，但他原则也是有限的。所谓有原则是指：分数高的一定比分数低的能拿到更多的糖果且分数 一样的拿到的糖果一样多；所谓原则是有限的又是指：刚刚说的原则仅对排队中相邻的两人生效，且允许有人拿不到糖果（杨主席是个穷逼）。
杨主席并不想多花一分钱买额外的糖，于是他想知道在各种情况下最少需要购入几块糖。
输入描述
首先是一个整数T，表示数据输入的组数，T<=20。
对于每组数据，有两行：
（1）一个整数n，表示队列中的人数，0 < n <= 1000。
（2）n个整数a[0] ... a[n-1]，表示按队列顺序每个人的得分，注意可能会有同分的情况，保证a[i]是int类型的。
输出描述
对应T行，每行即对应每组输入的最少购入糖数结果。
示例1
输入:
2 6 12 13 14 5 10 13 6 2 2 2 2 2 2
输出:
6 0
C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 480K, 提交时间: 2019-04-23 09:46:15
#include<stdio.h>
#include<string.h>
#include<bits/stdc++.h>
using namespace std;
int main(){
int T,n;
int a[1001],b[1001],c[1001];
int i,j;
scanf("%d",&T);
while(T--){
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(i=2;i<=n;i++){
if(a[i]>a[i-1])
b[i]=b[i-1]+1;
if(a[i]==a[i-1])
b[i]=b[i-1];
}
for(i=n-1;i>=1;i--){
if(a[i]>a[i+1])
c[i]=c[i+1]+1;
if(a[i]==a[i+1])
c[i]=c[i+1];
}
int sum=0;
for(i=1;i<=n;i++){
sum+=max(b[i],c[i]);
}
printf("%d\n",sum);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 11ms, 内存消耗: 460K, 提交时间: 2019-04-24 16:24:15
#include <iostream>
using namespace std;
int main() {
int t,a[1005],n,ans[25];
cin>>t;
for(int i=0;i<t;i++){
cin>>n;
int sum=0;
for(int j=0;j<n;j++){
cin>>a[j];
}
for(int j=0;j<n;j++){
int zuo=0,you=0;
for(int k=j;k>0;k--){
if(a[k]>a[k-1]){
zuo++;
}
if(a[k]<a[k-1]){
break;
}
}
for(int k=j;k<n-1;k++){
if(a[k]>a[k+1]){
you++;
}
if(a[k]<a[k+1]){
break;
}
}
sum+=max(zuo,you);
}
cout<<sum<<endl;
}
return 0;
}