P7701

题面

有

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

数组的预处理，可以用数据结构进行维护。

代码

CPP

#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;
}

文章操作

题面

题解

代码

相关推荐

评论

P7701