hdu_5805_NanoApe Loves Sequence(xjb搞)

题意：

给你n个数，现在要删一个数，删每个数的概率是一样的，现在问你删一个值后的相邻数绝对值最大差的期望是多少，因为担心精度误差，让你答案乘n

题解：

先算出不删数的绝对值最大的差ma并记录位置，如果要删的数不是刚才求出来的位置，那么ans+=max(abs(a[i-1]-a[i+1],ma)。如果是，那么重新求一下最大值就行了，因为最多重求两次，所以总复杂度还是O(n)。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 using namespace std;
 5 typedef long long ll;
 6 const int N=1e5+7;
 7 ll a[N];
 8 int t,n;
 9 
10 ll getnew()
11 {
12     ll an=0;
13     F(i,2,n)an=max(an,abs(a[i]-a[i-1]));
14     return an;
15 }
16 int main(){
17     
18     scanf("%d",&t);
19     while(t--)
20     {
21         scanf("%d",&n);
22         F(i,1,n)scanf("%I64d",a+i);
23         ll pos,ma=0;
24         F(i,2,n){
25             int tp=abs(a[i]-a[i-1]);
26             if(tp>ma)ma=tp,pos=i;
27         }
28         ll ans=0;
29         F(i,1,n)
30         {
31             if(i==pos||i==pos-1)
32             {
33                 if(i==1)
34                 {
35                     ll tp=a[i];
36                     a[i]=a[i+1];
37                     ans+=getnew();
38                     a[i]=tp;
39                 }else
40                 {
41                     ll tp=a[i];
42                     a[i]=a[i-1];
43                     ans+=getnew();
44                     a[i]=tp;
45                 }
46             }else
47             {
48                 if(i==1||i==n)ans+=ma;
49                 else{
50                     ans+=max(ma,abs(a[i+1]-a[i-1]));
51                 }
52             }
53             
54         }
55         printf("%I64d
",ans);
56     }
57     return 0;
58 }

View Code