题解
贪心，把产奶量，商店给出的收购价和村民给的租金均降序排序，然后遍历每一种方案，把牛分成两部分，使得一部分产奶，一部分卖出，看哪一种总收益最大。
代码稍微复杂，但思维难度不大。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
using namespace std;
typedef long long ll;
struct Sp{
int req, p1;
};
struct cmp{
inline bool operator() (const Sp &s1, const Sp &s2){
return s1.p1 > s2.p1;
}
};
struct cmp2{
inline bool operator() (const int &i1, const int &i2){
return i1 > i2;
}
};
Sp sp[100005];
int n, m, r, otp[100005], p2[100005];
ll totp[100005] = {0}, tmon[100005] = {0};
ll tr[100005] = {0};
int main(){
scanf("%d%d%d", &n, &m, &r);
for(int i = 0; i < n; ++i)
scanf("%d", &otp[i]);
for(int i = 0; i < m; ++i)
scanf("%d%d", &sp[i].req, &sp[i].p1);
for(int i = 0; i < r; ++i)
scanf("%d", &p2[i]);
sort(sp, sp + m, cmp());
sort(p2, p2 + r, cmp2());
sort(otp, otp + n, cmp2());
totp[0] = 0, tmon[0] = 0;
for(int i = 1; i <= m; ++i)
totp[i] = totp[i - 1] + sp[i - 1].req,
tmon[i] = tmon[i - 1] + 1ll * sp[i - 1].p1 * sp[i - 1].req;
tr[0] = 0;
for(int i = 1; i <= r; ++i)
tr[i] = tr[i - 1] + 1ll * p2[i - 1];
ll ans = tr[min(n, r)], curotp = 0;
for(int i = 0; i < n; ++i){
curotp += otp[i];
int ind = lower_bound(totp, totp + m + 1, curotp) - totp;
ans = max(ans, tmon[ind - 1] + (curotp - totp[ind - 1]) * sp[ind - 1].p1 + tr[min(n - i - 1, r)]);
}
printf("%lld\n", ans);
return 0;
}