牛客(多校8):Kabaleo Lite

题目链接

• 题目大意:
• 有n种菜,每种菜的数量为 bi , 每个菜的盈利为 ai.
• 每个顾客必须从第1种菜开始,连续地吃,每种吃一个。
• 保证顾客最多的情况下,盈利最大

• 题解:
bi 就是最大顾客数量。然后求盈利的前缀和,从大到小取即可。
• 注意结果会超出long long.
• 复杂度O(n) 或者 O(nlogn)都可以。

代码:

#include bits/stdc++.h
using namespace std;

const int MAXN = 100010;
int a[MAXN];
int b[MAXN];
long long suma[MAXN];
pairlong long, int pp[MAXN];
int sta[MAXN];+

const long long TT = 10000000LL;

int main() {
	int T;
	scanf("%d", T);
	int iCase = 0;
	while (T--) {
		int n;
		scanf("%d", n);
		suma[0] = 0;
		for (int i = 1; i = n; i++) {
			scanf("%d", a[i]);
			suma[i] = suma[i-1] + a[i];
			pp[i] = make_pair(suma[i], i);
		}
		for (int i = 1; i = n; i++) {
			scanf("%d", b[i]);
		}
		int top = 0;
		for (int i = 1; i = n; i++) {
			if (top == 0) sta[top++] = i;
			else if (b[sta[top-1]]  b[i]) sta[top++] = i;
		}
		sort(pp+1, pp+n+1);
		int ans1 = 0;
		int now = 0;
		long long pos1 = 0, pos2 = 0;
		long long neg1 = 0, neg2 = 0;
		
		for (int i = n; i = 1; i--) {
			long long c = pp[i].first;
			int id = pp[i].second;
			while (sta[top-1]  id) top--;

			int tmp = b[sta[top-1]] - ans1;
			if ((c = 0  tmp = 0) || (c = 0  tmp = 0)) {
				c = abs(c);
				tmp = abs(tmp);
				pos1 += (c/TT) * tmp;
				pos2 += (c%TT) * tmp;
				if (pos2 = TT) {
					pos1 += pos2 / TT;
					pos2 %= TT;
				}
			} else {
				c = abs(c);
				tmp = abs(tmp);
				neg1 += (c/TT) * tmp;
				neg2 += (c%TT) * tmp;
				if (neg2 = TT) {
					neg1 += neg2 / TT;
					neg2 %= TT;
				}
			}

			ans1 = b[sta[top-1]];
		}
		iCase++;
		printf("Case #%d: %d ", iCase, ans1);

		if (pos1  neg1 || (pos1 == neg1  pos2 = neg2)) {
			pos2 -= neg2;
			if (pos2  0) {
				pos2 += TT;
				pos1--;
			}
			pos1 -= neg1;
			if (pos1 == 0) printf("%lld\n", pos2);
			else printf("%lld%07lld\n", pos1, pos2);
		} else {
			neg2 -= pos2;
			if (neg2  0) {
				neg2 += TT;
				neg1--;
			}
			neg1 -= pos1;
			printf("-");
			if (neg1 == 0) printf("%lld\n", neg2);
			else printf("%lld%07lld\n", neg1, neg2);
		}
	}
	return 0;
}
最新回复(0)
/jishu8mIsOySUh4R47tvr7ngwQshdKopRUbFZw2jcXw_3D_3D4794960
8 简首页