P7701

DDF_ · 2025-07-13 07:59:34 · 题解

题面

有 m 个人分布在 6 \times n 的座位中，这 m 人按顺序从它的座位走到位于中央的走廊，然后往前或往后走进第一排前或最后一排后的一个房间。设对于一个人，它经过的人数为 x，房间里人数为 y，那么它的不满度为 Ax+By。最小化所有人不满度的和。

题解

你好。

可以发现按顺序这一点很重要，由此推出对于每个人，它往前往后走所经过的人数总是不变。

所以可以预处理第 i 个人往前走的代价 a_{i}，往后走的代价 b_{i}。

然后，若上面的房间有 x 个人，则下面的房间就有 m-x 个人，这样的代价为 A(\sum_{i=0}^{x-1}i+\sum_{i=0}^{m-x-1}i)，可以用等差数列求和公式直接推出。

于是就可以这样想：若 m 个人全都去前面的房间，我们要从中抽取 x 个人去后面的房间，那么如何使代价最小。

从贪心的角度，可以发现选取能省代价最多的 x 个人即可，于是将 a 数组和 b 数组按照 a_{i}-b_{i} 排序。

接着，枚举 x \in [0,m]，前 x 个去后面，后 m-x 个去前面，预处理排序后 a_{i} 和 b_{i} 的前缀和，就可以完整地计算代价了。

对于 a 和 b 数组的预处理，可以用数据结构进行维护。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+2;
ll n,m;
char s[10];
ll A,B,ans;
ll tr[N];
bool mp[N][8];
struct node{
    ll a,b;
} p[6*N];
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;
    return;
}
ll sum(int x) {
    int sum=0;
    for(int i=x;i;i-=lowbit(i)) sum+=tr[i];
    return sum;
}
bool cmp(node a,node b) {
    return (a.a-a.b)>(b.a-b.b);
}
int main() {
    scanf("%lld%lld%lld%lld",&n,&m,&A,&B);
    for(int i=1;i<=n;i++) {add(i,2);for(int j=1;j<=6;j++) mp[i][j]=true;}
    for(int i=1;i<=m;i++) {
        cin>>s;
        int x=0,y=s[strlen(s)-1]-'A'+1;
        for(int i=0;i<strlen(s)-1;i++) x=x*10+s[i]-'0';
        if(y==1) p[i].a+=mp[x][2],p[i].b+=mp[x][2];
        if(y==6) p[i].a+=mp[x][5],p[i].b+=mp[x][5];
        if(y==3||y==4) add(x,-1);
        mp[x][y]=false;
        p[i].a+=sum(x),p[i].b+=sum(n)-sum(x-1);
    }
    sort(p+1,p+1+m,cmp);
    for(int i=1;i<=m;i++) p[i].a+=p[i-1].a,p[i].b+=p[i-1].b;
    ans=1e16;
    for(ll i=0;i<=m;i++) ans=min(ans,A*(p[i].b+p[m].a-p[i].a)+B*(i*(i-1ll)/2ll+(m-i-1ll)*(m-i)/2ll));
    printf("%lld",ans);
    return 0;
}