【APIO2015】Palembang Bridges-白红宇

【APIO2015】Palembang Bridges

阅读量：5011 次

发布时间：2019-06-12

本文共 12020 字，大约阅读时间需要 40 分钟。

题目描述

一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 $A$ 和区域 $B$。

每一块区域沿着河岸都建了恰好 $1000000001$ 栋的建筑，每条岸边的建筑都从 $0$ 编号到 $1000000000$。相邻的每对建筑相隔 $1$ 个单位距离，河的宽度也是 $1$ 个单位长度。区域 $A$ 中的 $i$ 号建筑物恰好与区域 $B$ 中的 $i$ 号建筑物隔河相对。

城市中有 $N$ 个居民。第 $i$ 个居民的房子在区域 $P_i$ 的 $S_i$ 号建筑上，同时他的办公室坐落在 $Q_i$ 区域的 $T_i$ 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，政府决定建造不超过 $K$ 座横跨河流的大桥。

由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。

当政府建造最多 $K$ 座桥之后，设 $D_i$ 表示第 $i$ 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁，使得 $D_1 + D_2 + \dots + D_N$ 最小。

输入格式

输入的第一行包含两个正整数 $K$ 和 $N$，分别表示桥的上限数量和居民的数量。

接下来 $N$ 行，每一行包含四个参数：$P_i, S_i, Q_i$ 和 $T_i$，表示第 $i$ 个居民的房子在区域 $P_i$ 的 $S_i$ 号建筑上，且他的办公室位于 $Q_i$ 区域的 $T_i$ 号建筑上。

输出格式

输出仅为一行，包含一个整数，表示 $D_1 + D_2 + \dots + D_N$ 的最小值。

子任务

所有数据都保证：$P_i$ 和 $Q_i$ 为字符 “A” 和 “B” 中的一个， $0 \leq S_i, T_i \leq 1000000000$，同一栋建筑内可能有超过 $1$ 间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 $1$）。

子任务 1 （8 分）
- $K = 1$
- $1 \leq N \leq 1000$

子任务 2 （14 分）
- $K = 1$
- $1 \leq N \leq 100000$

子任务 3 （9 分）
- $K = 2$
- $1 \leq N \leq 100$

子任务 4 （32 分）
- $K = 2$
- $1 \leq N \leq 1000$

子任务 5 （37 分）
- $K = 2$
- $1 \leq N \leq 100000$

分析1

我们先考虑$m=1$的时候的做法

对于子任务1，首先把所有的坐标离散出来，最多有$2n$个

然后暴力枚举$2n$的坐标的位置造桥，再$O(n)$计算代价

时间复杂度$O(2n^2)$，期望得分8分

紧接着考虑优化，我们发现，不需要每次花费$O(n)$来计算代价

我们只需要把所有的区间离散到坐标上，然后顺着扫一遍，直接记录一下，每次就可以$O(1)$修改得到代价

时间复杂度$O(2n)$，期望得分22分

#include
    
       #include
     
        #include
      
         #include
       
          #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define LL long long#define pii pair
               
                #define mp make_pair using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++;} inline void read(int &x){ char c=nc();int b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;} inline void read(LL &x){ char c=nc();LL b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;} inline int read(char *s){ char c=nc();int len=1; for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0; for(;(c>='a' && c<='z');s[len++]=c,c=nc()); s[len++]='\0'; return len;} inline void read(char &x){ for (x=nc();!(x>='A' || x<='B');x=nc());} int wt,ss[19];inline void print(int x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else { for (wt=0;x;ss[++wt]=x%10,x/=10); for (;wt;putchar(ss[wt]+48),wt--);}}inline void print(LL x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}}int n,m,k;LL b[2000010];LL c[2000010],d[2000010];struct data{ int xa,xb; LL ya,yb;}a[1000010];int Hash(int x){ return lower_bound(b+1,b+1+k,x)-b;}int main(){ read(m);read(n); char ch;k=0; for (int i=1;i<=n;i++) { read(ch),read(a[i].ya),a[i].xa=ch-'A'+1,b[++k]=a[i].ya, read(ch),read(a[i].yb),a[i].xb=ch-'A'+1,b[++k]=a[i].yb; if (a[i].ya>a[i].yb) swap(a[i].ya,a[i].yb),swap(a[i].xa,a[i].xb); } sort(b+1,b+1+k); k=unique(b+1,b+1+k)-b-1; if (n<=1000 && m==1) { LL res=(LL)(1e17),s; for (int i=1;i<=k;i++) { s=0; for (int j=1;j<=n;j++) if (a[j].xa==a[j].xb) s+=a[j].yb-a[j].ya; else if (a[j].ya<=b[i] && a[j].yb>=b[i]) s+=a[j].yb-a[j].ya+1LL; else if (b[i]

分析2

然后在思考$m=2$做法的时候，猛然醒悟...自己原来是个煞笔...

我们在回过头去看$m=1$的时候

我们发现，答案由两部分组成，当两个建筑位于同一侧的时候$ans1=|S_i-T_i|$，显然$ans1$是固定的

而第二部分的答案$ans2=\sum |P_i-x|+|T_i-x|+1$，$x$表示桥的位置，显然当$x$集合${S_i,T_i}$的中位数的时候$ans2$取得最小值

时间复杂度$O(nlogn)$，期望得分22

#include
    
       #include
     
        #include
      
         #include
       
          #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define LL long long#define pii pair
               
                #define mp make_pair using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++;} inline void read(int &x){ char c=nc();int b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;} inline void read(LL &x){ char c=nc();LL b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;} inline int read(char *s){ char c=nc();int len=1; for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0; for(;(c>='a' && c<='z');s[len++]=c,c=nc()); s[len++]='\0'; return len;} inline void read(char &x){ for (x=nc();!(x>='A' || x<='B');x=nc());} int wt,ss[19];inline void print(int x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else { for (wt=0;x;ss[++wt]=x%10,x/=10); for (;wt;putchar(ss[wt]+48),wt--);}}inline void print(LL x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}}int n,m,k;LL b[2000010];LL c[2000010],d[2000010];struct data{ int xa,xb; LL ya,yb;}a[1000010];int main(){ read(m);read(n); char ch;k=0; for (int i=1;i<=n;i++) { read(ch),read(a[i].ya),a[i].xa=ch-'A'+1; read(ch),read(a[i].yb),a[i].xb=ch-'A'+1; if (a[i].xa!=a[i].xb) b[++k]=a[i].ya,b[++k]=a[i].yb; if (a[i].ya>a[i].yb) swap(a[i].ya,a[i].yb),swap(a[i].xa,a[i].xb); } sort(b+1,b+1+k); if (m==1) { LL x=b[k/2+1],res=0; for (int i=1;i<=n;i++) if (a[i].xa==a[i].xb) res+=a[i].yb-a[i].ya; else if (a[i].ya<=x && a[i].yb>=x) res+=a[i].yb-a[i].ya+1; else if (a[i].ya>x) res+=a[i].yb-a[i].ya+1+2*(a[i].ya-x); else res+=a[i].yb-a[i].ya+1+2*(x-a[i].yb); print(res),puts(""); } return 0;}

分析3

考虑$m=2$的做法

对于子任务3，同上述一样离散以后，暴力枚举两座桥的位置，然后花费$O(n)$计算代价

时间复杂度$O(4n^3)$，期望得分9分

继续考虑，我们可以发现，当有两座桥的时候，所有的居民唯一需要做的就是，找一座代价小的桥

而对于每一个居民而言，代价$ans=|P_i-x|+|T_i-x|$，$x$为桥的位置，即如下图

那么，增加相同的距离，也就是说，我们需要比较$\frac {P_i+T_i}{2}$距离哪个比较近即可

这样，我们如果把所有的居民按照$\frac {P_i+T_i}{2}$排序的话，我们可以把所有的居民分成连续的两段，前一段使用前一座桥，后一段时候后一座桥

那么，我们把$m=2$问题，规约成了两个$m=1$问题

枚举断点，暴力的做$m=1$问题即可

时间复杂度$O(n^2logn)$，期望得分41分，合并第一部分，可以得到63分，是一个很可观的分数了

#include
    
       #include
     
        #include
      
         #include
       
          #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define LL long long#define pii pair
               
                #define mp make_pair using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++;} inline void read(int &x){ char c=nc();int b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;} inline void read(LL &x){ char c=nc();LL b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;} inline int read(char *s){ char c=nc();int len=1; for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0; for(;(c>='a' && c<='z');s[len++]=c,c=nc()); s[len++]='\0'; return len;} inline void read(char &x){ for (x=nc();!(x>='A' || x<='B');x=nc());} int wt,ss[19];inline void print(int x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else { for (wt=0;x;ss[++wt]=x%10,x/=10); for (;wt;putchar(ss[wt]+48),wt--);}}inline void print(LL x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}}int n,m,k;LL b[2000010];vector
                
                  e;LL c[2000010],d[2000010];struct data{ int xa,xb; LL ya,yb;}a[1000010];bool cmp(data x,data y){ return x.ya+x.yb
                 
                  a[x].yb) swap(a[x].ya,a[x].yb),swap(a[x].xa,a[x].xb); } n=x; sort(b+1,b+1+k); if (m==2 && n<=1000) { sort(a+1,a+1+n,cmp); LL res=(LL)1e17,s,y; for (int x=1;x<=n+1;x++) { s=0; if (x>1) { e.clear(); for (int i=1;i

分析4

继续考虑$m=2$的满分做法

我们得想办法把找中位数和算$\sum |P_i-x|+|T_i-x|+1$加速

我们每次会加入两个数字，或者删除两个数字，需要动态的维护中位数和上面的绝对值之和

用线段树来维护，很容易维护出中位数

那么绝对值怎么处理？显然，把绝对值拆开，因为，维护中位数的时候，顺便记录下中位数之前的和，然后就可以做啦

时间复杂度$O(nlogn)$，期望得分100

满分程序

我的线段树写的比较丑QAQ

#include
    
       #include
     
        #include
      
         #include
       
          #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define LL long long#define pii pair
               
                #define mp make_pair using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++;} inline void read(int &x){ char c=nc();int b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;} inline void read(LL &x){ char c=nc();LL b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;} inline int read(char *s){ char c=nc();int len=1; for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0; for(;(c>='a' && c<='z');s[len++]=c,c=nc()); s[len++]='\0'; return len;} inline void read(char &x){ for (x=nc();!(x>='A' || x<='B');x=nc());} int wt,ss[19];inline void print(int x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else { for (wt=0;x;ss[++wt]=x%10,x/=10); for (;wt;putchar(ss[wt]+48),wt--);}}inline void print(LL x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}}int n,m,k;LL b[200010];LL c[200010],d[200010];struct data{ int xa,xb; LL ya,yb;}a[100010];struct ST{ int sum;LL x;}s1[800010],s2[800010];int Hash(int x){ return lower_bound(b+1,b+1+k,x)-b;}void change1(int q,int l,int r,int x,int y,LL z){ if (l==r) {s1[x].sum+=y;s1[x].x+=z;return ;} int mid=l+r>>1; if (q<=mid) change1(q,l,mid,x<<1,y,z);else change1(q,mid+1,r,x<<1|1,y,z); s1[x].sum=s1[x<<1].sum+s1[x<<1|1].sum; s1[x].x=s1[x<<1].x+s1[x<<1|1].x;}void change2(int q,int l,int r,int x,int y,LL z){ if (l==r) {s2[x].sum+=y;s2[x].x+=z;return ;} int mid=l+r>>1; if (q<=mid) change2(q,l,mid,x<<1,y,z);else change2(q,mid+1,r,x<<1|1,y,z); s2[x].sum=s2[x<<1].sum+s2[x<<1|1].sum; s2[x].x=s2[x<<1].x+s2[x<<1|1].x;}int query1(int q,int l,int r,int x){ if (l==r) return b[l]; int mid=l+r>>1; if (s1[x<<1].sum>=q) return query1(q,l,mid,x<<1); return query1(q-s1[x<<1].sum,mid+1,r,x<<1|1);}int query2(int q,int l,int r,int x){ if (l==r) return b[l]; int mid=l+r>>1; if (s2[x<<1].sum>=q) return query2(q,l,mid,x<<1); return query2(q-s2[x<<1].sum,mid+1,r,x<<1|1);}LL sum1(int q,int l,int r,int x){ if (l==r) return s1[x].x; int mid=l+r>>1; if (s1[x<<1].sum>=q) return sum1(q,l,mid,x<<1); return s1[x<<1].x+sum1(q-s1[x<<1].sum,mid+1,r,x<<1|1);}LL sum2(int q,int l,int r,int x){ if (l==r) return s2[x].x; int mid=l+r>>1; if (s2[x<<1].sum>=q) return sum2(q,l,mid,x<<1); return s2[x<<1].x+sum2(q-s2[x<<1].sum,mid+1,r,x<<1|1);}LL num1(int q,int l,int r,int x){ if (l==r) return s1[x].sum; int mid=l+r>>1; if (s1[x<<1].sum>=q) return num1(q,l,mid,x<<1); return s1[x<<1].sum+num1(q-s1[x<<1].sum,mid+1,r,x<<1|1);}LL num2(int q,int l,int r,int x){ if (l==r) return s2[x].sum; int mid=l+r>>1; if (s2[x<<1].sum>=q) return num2(q,l,mid,x<<1); return s2[x<<1].sum+num2(q-s2[x<<1].sum,mid+1,r,x<<1|1);}bool cmp(data x,data y){ return x.ya+x.yb
                
                 a[x].yb) swap(a[x].ya,a[x].yb),swap(a[x].xa,a[x].xb); } n=x; sort(b+1,b+1+k); if (m==1) { LL x=b[k/2+1],res=0; for (int i=1;i<=n;i++) if (a[i].ya<=x && a[i].yb>=x) res+=a[i].yb-a[i].ya+1; else if (a[i].ya>x) res+=a[i].yb-a[i].ya+1+2*(a[i].ya-x); else res+=a[i].yb-a[i].ya+1+2*(x-a[i].yb); print(res+S),puts(""); } if (m==2) { memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); sort(a+1,a+1+n,cmp); LL res=(LL)1e17,s,y,z,t,p=0,q=0; for (int i=1;i<=n;i++) change2(Hash(a[i].ya),1,k,1,1,a[i].ya),change2(Hash(a[i].yb),1,k,1,1,a[i].yb),q+=2LL; for (int x=1;x<=n+1;x++) { s=0; if (x>1) { y=query1(p/2+1,1,k,1); z=sum1(p/2+1,1,k,1); t=num1(p/2+1,1,k,1); s+=y*t-z+(s1[1].x-z)-y*(p-t)+(LL)(x-1); } if (x<=n) { y=query2(q/2+1,1,k,1); z=sum2(q/2+1,1,k,1); t=num2(q/2+1,1,k,1); s+=y*t-z+(s2[1].x-z)-y*(q-t)+(LL)(n-x+1); } if (x<=n) { change1(Hash(a[x].ya),1,k,1,1,a[x].ya),change1(Hash(a[x].yb),1,k,1,1,a[x].yb);p+=2LL; change2(Hash(a[x].ya),1,k,1,-1,-a[x].ya),change2(Hash(a[x].yb),1,k,1,-1,-a[x].yb);q-=2LL; } res=min(res,s); } print(res+S),puts(""); } return 0;}