标签：string   algo   char   sprintf   str   push   www.   clu   out   

APIO2015 八邻旁之桥

题意：

? 自己看

题解：

? 校内模拟赛做到这题，数据范围崩了，\(K=21\)???好吧\(或K=1或2\)。切了。

? 先判在一侧的情况。\(K=1\)桥显然在所有端点位置的中位数。\(K=2\)时，我们发现一个人总会走离\(\frac{S_i+T_i}{2}\)近的那座桥，那就按\(\frac{S_i+T_i}{2}\)排序，权值线段树在线插入&维护中位数就没了。

#include
#include
#include
#include
#define fo(i,l,r) for(int i=l;i=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
using namespace std;
typedef long long ll;
typedef pair pii;
#define P(a,b) make_pair(a,b)
inline void open(const char *s)
{
    #ifndef ONLINE_JUDGE
    char str[20];
    sprintf(str,"in%s.txt",s);
    freopen(str,"r",stdin);
//  sprintf(str,"out%s.txt",s);
//  freopen(str,"w",stdout);
    #endif
}
inline ll rd()
{
    static ll x,f;
    x=0;f=1;
    char ch=getchar();
    for(;ch'9';ch=getchar())if(ch=='-')f=-1ll;
    for(;ch>='0'&&ch0?x:-x;
}
const int N=100010;
const ll Inf=1e18;
int n,K,tt=0;
ll ans=0;
char s1[10],s2[10];
 
inline int fabs(int a){return a>1;
    sort(a+1,a+tt+1);
    int pos=a[tt>>1];
    fo(i,1,tt)ans+=fabs(a[i]-pos);
    printf("%lld\n",ans);
}
 
}
 
namespace K2{
struct node{ll x,y;double val;}a[N];
ll v[N>1;
    build(lson);build(rson);
    pushup(o);
}
void modify(int o,int l,int r,int x)
{
    if(l==r){
        tr[o].siz[1]--;
        tr[o].sum[1]-=v[l];
        tr[o].siz[0]++;
        tr[o].sum[0]+=v[l];
        return;
    }
    int mid=(l+r)>>1;
    if(x>1;
    if(tr[tr[o].ls].siz[t]>=k){
        sz[1]+=tr[tr[o].rs].siz[t];
        sm[1]+=tr[tr[o].rs].sum[t];
        return querys(lson,k,t);
    }
    sz[0]+=tr[tr[o].ls].siz[t];
    sm[0]+=tr[tr[o].ls].sum[t];
    return querys(rson,k-tr[tr[o].ls].siz[t],t);
}
 
}
 
inline void gao()
{
    ll x,y;
    fo(i,1,n){
        scanf("%s",s1);x=rd();
        scanf("%s",s2);y=rd();
        if(s1[0]==s2[0]){ans+=fabs(x-y);continue;}
        a[++tt].x=x;a[tt].y=y;a[tt].val=(x+y)*.5;
        v[++nn]=x;v[++nn]=y;
    }
    if(!tt)return void(printf("%lld\n",ans));
    ans+=tt;
    sort(v+1,v+nn+1);nn=unique(v+1,v+nn+1)-v-1;
    fo(i,1,tt){
        a[i].x=lower_bound(v+1,v+nn+1,a[i].x)-v;
        a[i].y=lower_bound(v+1,v+nn+1,a[i].y)-v;
        c[a[i].x]++;c[a[i].y]++;
    }
    sort(a+1,a+tt+1,cmp);
    Seg::build(rt,1,nn);
    ll mn=Inf,tmp;pii res;
//  fo(i,1,tt)printf("%d %d %.2lf\n",a[i].x,a[i].y,a[i].val);
//  fo(i,1,nn)printf("%d ",v[i]);puts("");
    fo(i,1,tt){
        Seg::modify(rt,1,nn,a[i].x);
        Seg::modify(rt,1,nn,a[i].y);
         
        tmp=0;sz[0]=sz[1]=sm[0]=sm[1]=0;
        x=Seg::querys(rt,1,nn,i,0);
        tmp+=sz[0]*x-sm[0]+sm[1]-x*sz[1];
         
        if(i!=tt){
            sz[0]=sz[1]=sm[0]=sm[1]=0;
            x=Seg::querys(rt,1,nn,tt-i,1);
            tmp+=sz[0]*x-sm[0]+sm[1]-x*sz[1];
        }
        mn=min(tmp,mn);
    }
    ans+=mn;
    printf("%lld\n",ans);
}
 
}
 
int main()
{
    open("c");
    K=rd();n=rd();
    if(K==1)K1::gao();
    else K2::gao();
    return 0;
}

APIO2015 八邻旁之桥

标签：string   algo   char   sprintf   str   push   www.   clu   out   

原文地址：https://www.cnblogs.com/JackyhhJuRuo/p/9837430.html