gym-102392E

题目链接

gym-102392E

思路

首先按照年龄把这些人排好序。读题后发现答案为carpc+mpm+t*(需要变化的年龄),显然我们枚举车的数量后就可以知道m的大小，然后再求出最小的变化年龄就可以了。
处理四个数组

long long mned[N],msum[N],cned[N],csum[N];
/*
mned表示前i个全都乘坐单车需要多少变化的年龄
msum表示前i个全都乘坐单车多出多少年龄
cned表示前i个全部乘坐小车需要多少变化的年龄
csum表示前i个全部乘坐小车多出多少年龄
*/

然后车上的人的年龄我们可以任意取min(d,a[j]-1)，再加上多出的年龄判断是否大于需要的年龄，大于的话就更新答案，不大于则不管。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 2e5+10;
ll mned[N],msum[N],cned[N],csum[N];
int a[N];
ll query(ll presum[],int l,int r){
	return presum[l]-presum[r+1];
}
int main(){
	int n,k,lc,lm,pm,pc,t,d;
	cin>>n>>k;
	cin>>lc>>pc>>lm>>pm;
	cin>>t>>d;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	mned[n]=msum[n]=cned[n]=csum[n]=0;
	for(int i=n-1;i>=0;i--){
		mned[i]=mned[i+1]+max(lm-a[i],0);
		msum[i]=msum[i+1]+max(a[i]-lm,0);
		cned[i]=cned[i+1]+max(lc-a[i],0);
		csum[i]=csum[i+1]+max(a[i]-lc,0);
	}
	ll sum = 0;
	ll ans = __LONG_LONG_MAX__;
	//枚举car的数量 
	for(int c=0;c*k<n;c++){
		int m = n-c*k;//骑单车的还需要几人
		//求出被小汽车载的人多出来的年龄，每次多一辆车就多出来很多年龄 
		for(int j=max(0,(c-1)*(k-1));j<c*(k-1);j++){
			sum+=min(d,a[j]-1);
		}
		if(sum+query(msum,n-m-c,n-c-1)+query(csum,n-c,n-1)>=query(mned,n-m-c,n-c-1)+query(cned,n-c,n-1)){
			ll price = 1ll*(query(mned,n-m-c,n-c-1)+query(cned,n-c,n-1))*t+1ll*pc*c+1ll*pm*m;
			ans=min(ans,price);
	    }
	}
	int c=(n+k-1)/k;
	sum = 0;
	for(int i=0;i<n-c;i++)sum+=min(d,a[i]-1);
	if(sum+query(csum,n-c,n-1)>=query(cned,n-c,n-1)){
		ll price = 1ll*query(cned,n-c,n-1)*t+1ll*pc*c;
		ans=min(ans,price);
	}
	if(ans==__LONG_LONG_MAX__)printf("-1\n");
	else printf("%lld\n",ans);
}