注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU313 中位数模型  

2012-10-07 10:33:26|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好题+难题一道
开了各种STL,写起来还是不顺手
看了xpd大神的题解耶
感觉好神的样子
学会了栈匹配模型
果然看题解比想题更爽(好吧,其实本题思路还是蛮显然的)
贴代码啦

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<iostream>
#include<stack>
using namespace std;

const int MAX=50000+10;
typedef long long LL;

int p1[MAX],p2[MAX],match[MAX],n,L;
map<int,int> delta,sum,p;
set< pair<int,pair< int,int> > > d;
stack< pair<int,int> > st;

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,cut;
cin>>n>>L;
for(i=1;i<=n;++i)
{
scanf("%d",&p1[i]);
delta[p1[i]]++;
d.insert(make_pair(p1[i],make_pair(-1,i)));
}
for(i=1;i<=n;++i)
{
scanf("%d",&p2[i]);
delta[p2[i]]--;
d.insert(make_pair(p2[i],make_pair(1,i)));
}
map<int,int>::iterator it,last;
for(it=delta.begin();it!=delta.end();++it)
{
sum[it->first]=it->second;
if(it!=delta.begin())
{
sum[it->first]+=sum[last->first];
p[sum[last->first]]+=it->first-last->first;
}
last=it;
}
p[sum[last->first]]+=L-last->first+delta.begin()->first;

int TOT=0;
for(it=p.begin();it!=p.end();++it)
{
TOT+=it->second;
}
int Ans=0,now=0;
for(it=p.begin();it!=p.end();++it)
{
if((now+it->second)*2>=TOT)
{
Ans=it->first;
break;
}
Ans=it->first;
now+=it->second;
}
for(it=delta.begin();it!=delta.end();++it)
{
if(sum[it->first]==Ans)
{
cut=it->first;
break;
}
}
set<pair<int,pair<int,int> > > ::iterator iter,ll;
set< pair<int,int> >::iterator tt;
for(iter=d.begin();iter!=d.end();++iter)
if(iter->first>cut)
break;
ll=iter;
if(ll==d.end())
ll=d.begin();
int stop=ll->second.second,stopy=ll->second.first;
for(iter=ll;1;)
{
if(st.size() && iter->second.first*st.top().second<0)
{
int a=iter->second.second,b=st.top().first;
if(iter->second.first==1)
swap(a,b);
match[a]=b;
st.pop();
}
else
st.push(make_pair(iter->second.second,iter->second.first));

++iter;
if(iter==d.end())
iter=d.begin();
if(iter->second.second==stop && iter->second.first==stopy)
break;
}
LL ans=0;
for(i=1;i<=n;++i)
{
LL x=p1[i],y=p2[match[i]];
if(x>y)swap(x,y);
ans+=min(y-x,L-y+x);
}
cout<<ans<<endl;
for(i=1;i<=n;++i)
cout<<match[i]<<" ";
cout<<endl;
return 0;
}




  评论这张
 
阅读(271)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018