我们在生命的路上常常绝望 大概是因为弯路走了太多
脚上的泡被磨起又磨破
像我们所有的幻想与梦 起起落落。
所以说 我这道题考场上面和题解想得一模一样啊啊啊啊啊啊啊啊啊啊！！！！！！
但是就是打复杂了啊啊啊啊啊啊啊啊！！！！！！！！！！！！！！！！！！！！
为什么我每次一看到环就感觉自己被耍了啊啊啊啊啊啊！！！！！！
自己的写法大概是有一个head tail记录环的首尾这样比较的时候就可以方便跳 然后我还加了一个-1的处理保证被合并了的不再被处理
考场上改了蛮久不过最后还是爆零啦
标程给出的方法是用了一个l数组和一个r数组
这个数被合并了就把它的r赋给左边的r
就相当于通过lr的操作把它挤掉
好无奈啊这么简单又机智的办法我居然没想到
因为lr数组那边处理起来还是有点问题所以标解是手打快排了的
这是标解
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<queue>
#define inf 2147483647
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define my long long
#define d "%lld"
using namespace std;
;
my getint();
my n;
my a[N+];
my w[N+];
my l[N+],r[N+];
my ans;
void qsort(my,my);
////////////在一个环中每次选择两个相邻元素，分数加上两个元素之差，然后把小的元素移除，问分数之和的最小值是多少
////////////贪心
//证明：
//对于当前环中最小值k以及k的相邻两个元素k_l,k_r
//把他与相邻数操作后一定是自己移除
//然后每次合并后留下的是最大值
//所以如果先合并k_l及k_l左边的元素或k_r及k_r右边的元素，那么合并后k相邻两个元素的值>=k_l,k_r
//所以首先合并k_l或k_r肯定更优
//然后肯定要合并min(k_l,k_r)
//然后直接删除k即可
int main()
{
fre("game");
n=getint();
;i<=n;i++) w[i]=i,a[i]=getint(),l[i]=i-,r[i]=i+;
l[]=n;r[n]=;
qsort(,n);
;T<n;T++) {
my i=w[T];
cout<<i<<" "<<l[i]<<" "<<r[i]<<" "<<a[i]<<endl;
ans+=min(a[l[i]],a[r[i]])-a[i];
l[r[i]]=l[i];r[l[i]]=r[i];
}
printf(d,ans);
;
}
my getint()
{
my w=;
;
char c=getchar();
') && c!='-') c=getchar();
,c=getchar();
+c-',c=getchar();
return q? -w:w;
}
void qsort(my l,my r)
{
my i=l,j=r,mid=a[w[(i+j)>>]];
while (i<=j) {
while (a[w[i]]<mid) i++;
while (a[w[j]]>mid) j--;
if (i<=j) {
w[]=w[i];
w[i]=w[j];
w[j]=w[];
i++;
j--;
}
}
if (i<r) qsort(i,r);
if (l<j) qsort(l,j);
}
然而作为一个彻头彻尾sort党很不服气
于是强行一波
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define N 100030
#define ll long long
using namespace std;
struct hh
{
ll v,id,l,r;
}a[N];
ll ans=,n;
ll b[N];
bool cmp(hh x,hh y){return x.v<y.v;}
int main(){
freopen ("game.in","r",stdin);
freopen ("game.out","w",stdout);
scanf ("%lld",&n);
;i<=n;++i){
scanf ("%lld",&a[i].v);
a[i].id=i,a[i].l=i-,a[i].r=i+;
}
a[].l=n,a[n].r=;
sort(a+,a+n+,cmp);
;i<=n;++i) b[a[i].id]=i;
;i<n;++i){
ans+=min(a[b[a[i].l]].v,a[b[a[i].r]].v)-a[i].v;
a[b[a[i].r]].l=a[i].l,a[b[a[i].l]].r=a[i].r;
}
cout<<ans;
;
}
那么这个悲惨的故事告诉我们处理问题的时候尽量简化
因为想多了要处理的细节多了反而瞬间爆炸
还不如把事情最简化一下