[CEOI2017] Sure Bet(双指针)

题目大意:

给出两个数组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;
}