F.拿物品
题意
有n个数每个数 ai bi两个属性
两人轮流拿 A先
A最后获得的分数为 他拿到的所有物品中ai的和
B最后获得的分数为 他拿到的所有物品中bi的和
两人都想比对方分高问两者怎么拿输出他们拿到的物品
题解
假设物品已经被选完，此时 牛牛选择的物品 A 属性的价值和是 N ， 牛可乐选择的物品 B 属性价值和是 M 。 如果 牛牛的 (a1,b1)物品与 牛可乐的 (a2,b2)( 交换，则 N′=N−a1+a2,M′=M+b1−b2 ，对于 牛牛（目标是最大化 N−M ）来说会变得更优仅当 a1+b1<a2+b2 （ N′−M′>N−M化简就能得到），对于 牛可乐也一样。所以两人都会优先选择 ai+bi 最大的物品。 将物品按照两个属性的和从大到小排序，依次分给两人即可。 除排序时间复杂度 O(n) 。
突破口从最后两者取到的价值交换后取得最优解的情况
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
| # include<bits/stdc++.h>
using namespace std;
# define endl '\n'
struct Data{
int a,b;
int pos;
}data[(int)2e5+5];
bool vis[(int)2e5+5];
bool cmp(Data x,Data y){return x.a+x.b>y.a+y.b;}
int main(){
int n;cin>>n;int cnt=0;
for(int i=0;i<n;i++)cin>>data[i].a,data[i].pos=i+1;
for(int i=0;i<n;i++)cin>>data[i].b;
sort(data,data+n,cmp);
vector<int>ans1,ans2;
bool turn=1;
for(int i=0;i<n;i++){
if(turn)ans1.push_back(data[i].pos);
else ans2.push_back(data[i].pos);
turn=!turn;
}
int len1=ans1.size(),len2=ans2.size();
for(int i=0;i<len1;i++)cout<<ans1[i]<<" ";
cout<<endl;
for(int i=0;i<len2;i++)cout<<ans2[i]<<" ";
}
|