标签：链表，贪心
题目
分析
暴力做法： 贪心，对于每个区间，从大到小排序，显然，wi大的对答案贡献越大 时间复杂度O(N^3 log N)
正解： 因为题目输出实数，所以当交换次数到一定时候，对答案的影响可以忽略不计 这个T大约是30次
对每个wi的贡献单独计算
每个wi只对相邻的T个产生贡献，所以取前后各T个
计算公式如下： \(w_i\sum_{x=1}^T\sum_{y=1}^T(l_{x-1}-l_x)*(r_y-r_{y-1})*\frac{1}{2^{x+y-1}}=2w_i(\sum_{x=1}^T(l_{x-1}-l_x)*\frac{1}{2^x})(\sum_{y=1}^T(r_y-r_{y-1})*\frac{1}{2^y})\)
将wi从小到大排序，然后计算完就从链表中无脑删除
时间复杂度为O(NT+N log N)
code
25分暴力
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=5e5+6;
double ans;
int n,w[maxn],bin[35];
inline bool cmp(int x,int y){return x>y;}
void work(int l,int r){
double t;int b[maxn],len=min(r-l+1,30);
rep(i,l,r)b[i-l+1]=w[i];
sort(b+1,b+r-l+2,cmp);
rep(i,1,len)t+=(double)b[i]/bin[i];
ans+=(double)t/(n*n);
//cout<<ans<<endl;
}
int main()
{
//freopen("T1.in","r",stdin);
//freopen("T1.out","w",stdout);
bin[1]=2;rep(i,2,30)bin[i]=bin[i-1]<<1;
//rep(i,1,30)cout<<bin[i]<<endl;
n=read();rep(i,1,n)w[i]=read();
rep(l,1,n)rep(r,l,n)work(l,r);
printf("%.4lf",ans);
return 0;
}
正解
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6;
int _pre[maxn],_next[maxn],n,l[36],r[36];
struct node{int id,val;}w[maxn];
double ans,bin[36];
inline bool cmp(node a,node b){return a.val<b.val;}
int main()
{
//freopen("T1.in","r",stdin);
//freopen("T1+.out","w",stdout);
n=read();rep(i,1,n)w[i].val=read(),w[i].id=i;
bin[0]=1;rep(i,1,30)bin[i]=bin[i-1]/2.0;
sort(w+1,w+1+n,cmp);
rep(i,1,n+1)_pre[i]=i-1;rep(i,0,n)_next[i]=i+1;
rep(i,1,n){
int lnow,rnow,llen=0,rlen=0;double lans=0,rans=0;
l[0]=r[0]=lnow=rnow=w[i].id;
rep(j,1,30){
if(lnow)l[++llen]=(lnow=_pre[lnow]);
if(rnow!=n+1)r[++rlen]=(rnow=_next[rnow]);
}
rep(j,1,llen)lans+=bin[j]*(l[j-1]-l[j]);
rep(j,1,rlen)rans+=bin[j]*(r[j]-r[j-1]);
ans+=lans*rans*2*w[i].val;
_pre[_next[w[i].id]]=_pre[w[i].id];
_next[_pre[w[i].id]]=_next[w[i].id];
}
printf("%.4lf",ans/n/n);
return 0;
}
