P7701 [CCC2014] 提前交卷 题解

· · 题解

Description

在一个教室里有 n 排座位，每排有 6 个，从左至右标号分别为 ABCDEF，其中 C 和 D 中有过道，通往教室前端和后端的两个房间，每个房间最开始没有人,每个座位上开始都有人。

有 m 个不同的学生会依次提前交卷，先从这一排走到过道上，在从过道走到前面或后面的房间里。每个提前交卷的学生有一个不满度，表示为 A\times x+B\times y，其中 A,B 是给定的常数，x 为经过的同学数量，由过道两侧的同学以及在过道与座位之间的同学组成（不包含自己）。y 为在到达房间前房间内的人数。

你需要安排这些学生是去前面还是后面的房间，求不满度之和的最小值。

Solution

画个图：

  前端
ABC||DEF
ABC||DEF
ABC||DEF
  后端

暴力就是 dp 求解。

本题最关键的性质就是在确定两个房间最终分别有多少人后，可以直接算出不满度中 B\times y 的部分，同时第 i 个人去前面和去后面的人数是确定的。

设前面的房间有 i 个人，后面的有 m-i 个人，那么不满度之和的后半部分就是 B\times(\dfrac{i\times(i-1)}{2}+\dfrac{(m-i)\times(m-i-1)}{2})。

求经过了多少人，就先将其分为两个部分，走到过道经过多少人就直接分讨当前座位的编号，开 vis_{i,j} 记录第 i 排第 j 个座位上还有没有人。过道上经过的人相当于一个前缀和，sum_i 表示从第 i 排走到教室前面经过的人数，如果在他之前过道上有人离开就实时更新，用树状数组维护。

注意如果他就是坐在过道上的，要先更新 sum 再算值，不然会把自己也算进去。

这样我们只需要判断一个学生是去前面还是去后面，设去前面不满度为 u_i，去后面为 d_i。

假设所有人都先去了前面，将每个学生的 u_i-d_i 从大到小排序，这样选前面 k 个去后面肯定更优，然后枚举 k 的所有情况（0\sim m），对于每种情况算出不满度之和，然后取最小即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
long long A,B;
long long tr[100010];
bool vis[100010][8];
struct node{
    long long u,d;
}a[100010];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int val){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i]+=val;
    }
}
long long query(int x){
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        ans+=tr[i];
    }
    return ans;
}
void read(int &x,int &y){  //特殊读入方式
    x=0;
    string s;
    cin>>s;
    for(int i=0;i<s.size()-1;i++){  //得出排数
        x=(x<<3)+(x<<1)+s[i]-'0';
    }
    y=s[s.size()-1]-'A'+1;
}
bool cmp(node x,node y){
    return (x.u-x.d)>(y.u-y.d);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>A>>B;
    for(int i=1;i<=n;i++){
        add(i,2);
        for(int j=1;j<=6;j++){
            vis[i][j]=1;
        }
    }
    long long tmp=0;
    for(int i=1;i<=m;i++){
        int x,y;
        read(x,y);
        if(y==1) tmp+=vis[x][2];  //走到过道上要经过多少人
        if(y==6) tmp+=vis[x][5];
        if(y==3||y==4) add(x,-1);  //在过道上就更新sum
        vis[x][y]=0;  //记得赋为0
        a[i].u+=query(x),a[i].d+=query(n)-query(x-1);  //去前面和去后面，后面减的x-1是因为这一排的sum也要算
        tmp+=a[i].u;  //全都去前面经过的人数
    }
    sort(a+1,a+1+m,cmp);
    long long sum=0,ans=tmp*A+m*(m-1)/2*B;  //k=0时的情况
    for(int i=1;i<=m;i++){
        sum+=a[i].u-a[i].d;  //更新经过的人数
        ans=min(ans,tmp*A-sum*A+(i*(i-1)/2)*B+((m-i)*(m-i-1)/2)*B);  //记得加上B*y的部分
    }
    cout<<ans<<endl;
    return 0;
}