雅礼集训 小c饮水记

链表乱搞题

Posted by yjjr's blog on January 18, 2018

标签:链表,贪心

题目

这里写图片描述 这里写图片描述 这里写图片描述

分析

暴力做法: 贪心,对于每个区间,从大到小排序,显然,wi大的对答案贡献越大 时间复杂度O(N^3 log N)

正解: 因为题目输出实数,所以当交换次数到一定时候,对答案的影响可以忽略不计 这个T大约是30次

对每个wi的贡献单独计算

每个wi只对相邻的T个产生贡献,所以取前后各T个

计算公式如下:

将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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr