[NOI.AC] candy

题意：求净利益。

思路：

其实我也不怎么懂题面。

不过这种题一般来说就是从最大的开始选。

所以考虑贪心。

那么代价如何处理呢？？

我们考虑两个序列同时选数，把代价每次记录到一个序列的和上，那么对于两次的净利益求最大即可。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define int long long

const int maxn = 100010;

int a[maxn];

int b[maxn];

inline int solve(int *a,int *b,int n,int W) {

	int sum_a = 0;

	int sum_b = 0;

	int ans = -999;

	for(int i = 1,tmp = 0;i <= n; ++i) {

		sum_a += a[i];

		while(tmp <= n && sum_b < sum_a) {

			sum_b += b[++tmp];

		}

		if(sum_a <= sum_b) {

			ans = max((ll)ans,sum_a - (ll)W * (i + tmp));

		}

	}

	return ans;

}

inline bool cmp(int a,int b) {

	return a > b;

}

int n,W;

signed main () {

	cin >> n >> W;

	for(int i = 1;i <= n; ++i) {

		cin >> a[i];

	}

	for(int i = 1;i <= n; ++i) {

		cin >> b[i];

	}

	sort(a + 1,a + n + 1,cmp);sort(b + 1,b + n + 1,cmp);

	int ans1 = solve(a,b,n,W);

	int ans2 = solve(b,a,n,W);

	printf("%lld\n",max(ans1,ans2));

	return 0;

}

巴特西

[NOI.AC] candy

最新文章

热门文章