洛谷 P1732 [TJOI2011]序列

P1732 [TJOI2011]序列

题目描述

一指数列A={a1, a2, …, an},根据数列A计算数列B={b1, b2, …, bn},其中：

求\sum\limits^n_{i=1} b_ii=1∑n​bi​

输入输出格式

输入格式：

第一行是一个正整数t,表示测试数据的组数。接下来有t行，每行表示一组测试数据。每行以一个正整数n开始，表示数列A中元素的个数；然后是n个非负整数，依次表示a1, a2, …, an的值。

0<t<=10

0<n<=100 000

0<= ai<=65 536

输出格式：

对于每组测试数据，输出数列B的所有的元素之和。

输入输出样例

输入样例#1： 

2

5 1 2 3 4 5

7 2 9 7 4 6 2 6

输出样例#1： 

5

14

思路：模拟。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int t,n;

long long ans;

struct nond{

    int num,pos;

}v[];

int cmp(nond a,nond b){

    if(a.num==b.num)    return a.pos<b.pos;

    return a.num<b.num;

}

int main(){

    scanf("%d",&t);

    while(t--){

        ans=;

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%d",&v[i].num),v[i].pos=i;

        sort(v+,v++n,cmp);

        for(int i=;i<=n;i++){

            if(v[i].pos==){ ans+=v[i].num;continue; }

            int l=i-,r=i+,bns=0x7f7f7f7f;

            while(v[l].pos>v[i].pos)    l--;

            while(v[r].pos>v[i].pos)    r++;

            if(l!=)    bns=min(bns,v[i].num-v[l].num);

            if(r!=n+)    bns=min(bns,v[r].num-v[i].num);

            ans+=bns;

        }

        cout<<ans<<endl;

    }

}