题目大意:
给出两个数组A,B,可以在两个数组选择任意多个数,代价为选择的数的数目,得到的奖励为在数组A和数组B中选择的数的两个总和较小的那个,求能得到的最大收益
思路:
1.先给两个数组分别由大到小排序后求前缀和,不难得出在数组A中选择i个数,数组B中选择j个数时,最大收益为:
min(a[i], b[j])-i-j
2.之后是i,j的选择,由于是取a[i],b[j]中的最小值,因此a[i]<=b[j]时,i++,反之a[i]>b[j]时,j++,即依靠双指针来求解
代码如下:
#include<bits/stdc++.h>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
typedef long long ll;
using namespace std;
#define N 100005
double a[N],b[N];
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
for(int i= 1; i <= n; i++) cin>>a[i]>>b[i];
//由大到小排序
sort(a,a+n+1);
sort(b,b+n+1);
reverse(a + 1, a + n + 1);
reverse(b + 1, b + n + 1);
//求前缀和
for (int i = 1; i <= n; i++) {
a[i] += a[i - 1];
b[i] += b[i - 1];
}
//双指针
double ans = 0;
for (int i = 0,j=0;j<=n;) {
if (a[i] <= b[j]&&i<n)i++;
else j++;
ans = max(ans, min(a[i], b[j]) - i - j );
}
printf("%.4f", ans);
return 0;
}