Fence

· · 个人记录

我们可以想象一个东西，叫做“贡献值”，指的是每一个板子相对于相邻的两个板子的一个特定的值。比方说：如下图：中间的红色板子明显低于其他的两个板子，所以我们在计算它的“友好值”的时候（我们把从左到右的三个板子的高度分别标为A/B/C），是A-B+C-B，等于说，中间的这个板子被减去了两次。于是我们可以把中间的板子的“贡献值”标为-2.

同理，对于下面这张图，左边的板子高于它，右边的板子低于它，我们算贡献值的时候，是A-B+B-C，可以说，B被抵消了。于是中间这个板子的贡献值为0。

同理，下面这张图的友好值为B-A+B-C，贡献值为2.

当我们计算左右端点的时候，如果说端点板子低于相邻的板子，则友好值为：A-B（或者C-B），它的贡献值为-1；当端点板子高于相邻的板子时，友好值为B-A（或者B-C）。

至此，我们发现，一个木板的贡献值有五种：-2 -1 0 1 2。我们要做的，只是对要操作的木板进行分类。

例如：我们输入一组数据：

10 
9  5  1  2  6  7  4  18  20  12   
10  40  20  30  50  70  80  100  1000  500

它的标准是9 5 1 2 6 7 4 18 20 12.

我们按照贡献值分一下类：

1 0 -2 0 0 2 -2 0 2

所以，我们要对输入数据的第三排进行排序，以达到每一个数据它在数组中的贡献值等于标准中的贡献值。

标程如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[300001],b[300001];
int ding,gu;
long long ans=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)   scanf("%d",&b[i]);
    sort(b+1,b+1+n);
    for(int i=2;i<n;i++){
        if(a[i]<a[i-1]&&a[i]<a[i+1])
            gu++,ans-=b[gu]*2;//求两端高中间低的点.  
        if(a[i]>a[i-1]&&a[i]>a[i+1])    
            ding++,ans+=b[n-ding+1]*2;//求两端低中间高的点
    }
    if(a[1]>a[2])   ding++,ans+=b[n-ding+1];//由于第一个和最后一个没有连接两个点，所以需要特判
        else gu++,ans-=b[gu];
    if(a[n]>a[n-1]) ding++,ans+=b[n-ding+1];
        else gu++,ans-=b[gu];
    cout<<ans;//输出就行
    return 0;

（以上标称出自此大佬@only_xiaohuang）

\color{red}\text{(20180813 $T3$)}