C. Choosing flowers
题意
m种花，每种都有无限多要买n支
第一次购买第i种花获得a[i]点hp值 之后购买这种花获得b[i]hp值
问最多能获得多少hp值
题解
假设最优策略里面选择了x1,x2,…xn种买了不止一支，其余的可能只卖了一支，就直接按照a的从大到小买，对于b的贡献，按照b排序，那么b序列的贡献
b[x1]>=b[x2]>=b[x3]…>=b[xn] 显然在购买总数不变的条件下买x1获得的hp值更多
所以只有可能最多有一种花买了大于1支其余都只买了1支
那么只需要找到是哪种花购买1次以上，对于购买了k次的花记为x，则我们会发现如果少购买一次bx，去购买一个ai（ai>bx)则会使得总数值更高，因此对于每种bx，我们在购买它之前需要把所有ai>bx的花都先买下来。因此可以先按照ai进行排序，然后记录下ai的前缀和sum[i]，之后枚举每一个bi，二分查找到最小的p使得ap>=bi(因为是按照a[i]升序)，剩下的n-(m-pos)支花就全部购买bi。
处理过程需要注意：
1.如果m-p>n，则最多只能购买sum[n]而不是sum[p]
2.如果 p>m说明不存在a[p]>b[i]全部买这种花最优
3.如果i<=p(因为是升序大的a[p]都靠后)，则说明当前bi对应的第一次购买ai还没有被购买，需要先购买一次ai，剩下的n-p-1次才能购买bi。
4.如果i>p，剩下的n-p次全部购买bi。
参考博客
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int mod=2e3;
const int Max=2e5+5;
P data[Max];
ll persum[Max],a[Max],b[Max];
int main(){
Turnoff;
int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++)cin>>data[i].first>>data[i].second;
sort(data+1,data+1+m);
for(int i=1;i<=m;i++)persum[i]=persum[i-1]+data[i].first,a[i]=data[i].first;
ll ans=0;
for(int i=1;i<=m;i++){
int pos=lower_bound(a+1,a+1+m,data[i].second)-(a+1);
int have=m-pos;
if(pos>m)ans=max(ans,data[i].second*(n-1)+data[i].first);
if(have>n)ans=max(ans,persum[m]-persum[m-n]);
else if(pos>=i)ans=max(ans,data[i].first+persum[m]-persum[pos]+data[i].second*(n-1-have));
else if(pos<i)ans=max(ans,persum[m]-persum[pos]+data[i].second*(n-have));
}
cout<<ans<<endl;
}
}
|
原先的贪心思路是全部选择一种花x,买完n支
然后贪心的选择用b[x] 换a[y] (a[y]>b[x]) 但是
2 3
100 1
100 1
1 101
这组样例说明了这样贪心不合理
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
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int mod=2e3;
const int Max=2e5+5;
struct Data{
ll a,b;
bool vis;
}data[Max];
bool cmpb(Data x,Data y){
if(x.b!=y.b)return x.b>y.b;
else return x.a>y.a;
}
bool cmpa(Data x,Data y){return x.a>y.a;}
int main(){
Turnoff;
int t;cin>>t;
while(t--){
int n,m,pos=0;cin>>n>>m;
for(int i=0;i<m;i++){
cin>>data[i].a>>data[i].b;
data[i].vis=0;
}
sort(data,data+m,cmpb);
data[0].vis=1;
ll ans=data[0].a+(n-1)*data[0].b;
ll maxb=data[0].b,maxa=data[0].a;
sort(data,data+m,cmpa);
while(n>1&&pos<m){
if(data[pos].vis)pos++;
else if(maxb<data[pos].a){
ans-=maxb;ans+=data[pos].a;
data[pos].a=data[pos].b;
pos++,n--;
}
else break;
}
if(n==1){
sort(data,data+m,cmpa);
for(int i=0;i<m;i++){
if(data[i].a>maxa){
ans-=maxa;
ans+=data[i].a;
break;
}
else break;
}
}
cout<<ans<<endl;
}
}
|