当前位置：首页 > news >正文

打卡信奥刷题（2938）用C++实现信奥题 P5800 [SEERC 2019] Life Transfer

news 2026/5/12 20:11:34

P5800 [SEERC 2019] Life Transfer

题目背景

注：「feli」是当地货币单位。

题目描述

在大都市 Nekoresti 中，有nnn个人已知年龄，第iii个人年龄为aia_iai。现在他们享受着假期，所以他们决定去 Pisiev 游览一个著名的博物馆 Koshkseum。他们可以通过开车或骑摩托车去：

一辆车可以载最多kkk个人（包括一个年龄不低于lcl_clc岁的司机和至多k−1k-1k−1个乘客）。一辆车的租金为pcp_cpcfeli。
一辆摩托车只能载111个人（年龄不低于lml_mlm岁）。一辆摩托车的租金为pmp_mpmfeli。

不幸的是，这些人不是很富裕，所以他们请求一名当地的大魔法师 Mewlin 来帮助他们。通过使用一种强大的魔法 Mucadabra，Mewlin 可以转移人们的年龄。形式化地说，他可以减少一个年龄为xxx的人的年龄，同时增加一个年龄为yyy的人的年龄同一数值（这两个人的年龄之和不变）。完成111岁的年龄的转移的花费是tttfeli。由于魔法的限制，魔法不能将一个人的年龄改变超过ddd（如果一个人的年龄为xxx，改变后的年龄只能在[x−d,x+d][x-d, x+d][x−d,x+d]区间内）。并且，年龄也不能低于111岁。

帮助这些人花费最少的钱从 Nekoresti 到 Pisiev 去旅游吧。

输入格式

第一行包含两个整数nnn和k (1≤n,k≤105)k \ (1 \leq n, k \leq 10^5)k(1≤n,k≤105)，代表旅游的人数和一辆车的最大载客数。

第二行包含四个整数lc,pc,lml_c, p_c, l_mlc,pc,lm和pm (1≤lm<lc≤105,1≤pm<pc≤105)p_m \ (1 \leq l_m < l_c \leq 10^5, 1 \leq p_m < p_c \leq 10^5)pm(1≤lm<lc≤105,1≤pm<pc≤105)，代表开车的最低年龄、一辆车的租金、骑摩托车的最低年龄、一辆摩托车的租金。

第三行包含两个整数ttt和d (0≤t,d≤105)d \ (0 \leq t, d \leq 10^5)d(0≤t,d≤105)，代表转移111岁的年龄的花费和魔法的转移改变量限制。

第四行包含nnn个整数a1,a2,…,an (1≤ai≤105)a_1, a_2, \dots, a_n \ (1 \leq a_i \leq 10^5)a1,a2,…,an(1≤ai≤105)，aia_iai代表第iii个人的年龄。

输出格式

输出一个数字，即让所有人到达目的地的最小花费。如果无解，输出−1-1−1。

输入输出样例 #1

输入 #1

2 2 18 1000 16 1 5 3 16 15

输出 #1

输入输出样例 #2

输入 #2

2 2 23 10 15 5 2 2 9 20

输出 #2

-1

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=100010;intusec[N],usem[N],ndc[N],ndm[N],use[N],a[N];signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intn,k;cin>>n>>k;intlc,pc,lm,pm,c,x;cin>>lc>>pc>>lm>>pm>>c>>x;for(inti=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);for(inti=1;i<=n;i++){usec[i]=usec[i-1],usem[i]=usem[i-1],ndc[i]=ndc[i-1],ndm[i]=ndm[i-1],use[i]=use[i-1];if(a[i]>lc)usec[i]+=min(x,a[i]-lc);if(a[i]>lm)usem[i]+=min(x,a[i]-lm);if(a[i]+x<lc)ndc[i]+=1e10;elseif(a[i]<lc)ndc[i]+=lc-a[i];if(a[i]+x<lm)ndm[i]+=1e10;elseif(a[i]<lm)ndm[i]+=lm-a[i];use[i]+=min(x,a[i]-1);}intans=1e18;for(inti=0;i*k<=n;i++){intnd=ndc[n]-ndc[n-i]+ndm[n-i]-ndm[i*(k-1)];intus=usec[n]-usec[n-i]+usem[n-i]-usem[i*(k-1)]+use[i*(k-1)];intcost=nd*c+pc*i+pm*(n-i*k);if(nd<=us)ans=min(ans,cost);}intnow=n/k+1;intnd=ndc[n]-ndc[n-now],us=usec[n]-usec[n-now]+use[n-now];intcost=now*pc+c*nd;if(nd<=us)ans=min(ans,cost);if(ans==1e18)cout<<-1;elsecout<<ans;}