摘要:转化性质进行贪心

「六省联考2017」期末考试

题面

题目分析

看到这个问题在稿纸上写了两点思路:

  • 已知每个学生的安格瑞程度仅与最后一科出成绩的有关.
  • 枚举最后出成绩在那一天.

考虑枚举最后出成绩在那一天如何实现,显然我们需要把出成绩在那一天之后的全部操作到在这一天之前.

用前缀和处理一下出成绩的原始时间,得出比某一天大和比某一天小的数目.

进行操作时,若$B<A$,那么用$B$操作肯定更优,全部都用$B$操作即可.

不然,则在能够使用的范围内用$A$操作,剩下的用$B$操作,能够使用的范围即为比这一天大的值的数目和比这一天小的值的数目的最小值,剩下的用$B$操作的就是比这一天大的数目减去比这一天小的数目与0取较大值.

然后对于每个时间更新答案即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=100010;
lxl A,B,C,n,m,ans;
lxl t[big],b[big],pret[big],preb[big],nxtb[big],prek[big],nxtk[big],sum[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
int main(void)
{
A=read(),B=read(),C=read();
n=read(),m=read();
for(R int i(1);i<=n;++i)t[i]=read(),++pret[t[i]];
for(R int i(1);i<=m;++i)b[i]=read(),++preb[b[i]],++nxtb[b[i]];
for(R int i(1);i<big;++i)pret[i]+=pret[i-1],sum[i]=sum[i-1]+pret[i-1];
for(R int i(1);i<big;++i)prek[i]=prek[i-1]+preb[i-1],preb[i]+=preb[i-1];
for(R int i(big-2);i;--i)nxtk[i]=nxtk[i+1]+nxtb[i+1],nxtb[i]+=nxtb[i+1];
for(R int i(1);i<big;++i)
{
lxl tmp=C*sum[i];
if(tmp>ans&&ans)break;
if(A<B)tmp+=std::min(nxtk[i],prek[i])*A,nxtk[i]-=prek[i],tmp+=std::max((lxl)0,nxtk[i])*B;
else tmp+=nxtk[i]*B;
if(!ans)ans=tmp;
ans=std::min(ans,tmp);
}
printf("%lld\n",ans);
return 0;
}