牛客第八场快餐店

序言：

考试考的这么差

还写什么啊！

好吧，既然都已经出来了，当然我就写了啊。

---

第二题 快餐店

在考试的时候，老师说要爆 l o n g l o n g long long longlong，然而我的思路不配我写这道题

然后我就去写第三题了

现在我来讲一讲思路

首先利润 a [ i ] a[i] a[i]的范围最大是1e19所以必定超long long 所以我们就可以用__int128, long double 高精之类的

然后因为最多可供 a [ 1 ] a[1] a[1]个人选择，因为是选择连续的物品

我们先求出前缀和，先用一个栈记录一下比只选第一个的利润大的点，保持栈中的单调递增

然后从栈顶开始计算，每次更新ans后要减去相应的物品，因为到这个点一定会用到前面的点

贪心思路：

因为所有人都必须吃第一盘菜，

所以 b 1 b_1 b1​就是最大的顾客数

所求的利润只要求一下前缀和然后取最大值就可以了…

AC代码

#include <bits/stdc++.h>
#define ll __int128

using namespace std;
const int maxn=100005;
ll a[maxn],sum[maxn];
int b[maxn];
stack<int> st;
const int INF=0x3f3f3f3f;
__int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
 
void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
int main(){
	int T,n;
	scanf("%d",&T);
	int cas = 1;
	while(T--){
		scanf("%d",&n);
		memset(sum,0,sizeof(sum));
		int ans1 = 0;
		ll ans2 = 0;
		for(int i = 1;i <= n;i++){
			a[i] = read();
			sum[i] = sum[i-1]+a[i];
		}
		int minn = INF;
		for(int i = 1;i <= n;i++){
			scanf("%d",&b[i]);
			minn = min(minn,b[i]);
			b[i] = minn;
		}
		ans1 = b[1];
		st.push(1);
		for(int i = 2;i <= n;i++){
			if(sum[i] > sum[st.top()]){
				st.push(i);
			}
		}
		ll pre = b[st.top()];
		ans2 += (ll)sum[st.top()] * (ll)b[st.top()];
		st.pop();
		while(st.size()){
			if(pre != b[st.top()]){
				ans2 += (ll)sum[st.top()] * (ll)(b[st.top()] - pre);
				pre = b[st.top()];
				st.pop();
			}
			else st.pop();
		}
		printf("Case #%d: %d ",cas++, ans1);
		print(ans2);
		printf("\n");
	}
	return 0;
}

---

序言：

考试考的这么差

还写什么啊！

好吧，既然都已经出来了，当然我就写了啊。

---

第二题 快餐店

在考试的时候，老师说要爆 l o n g l o n g long long longlong，然而我的思路不配我写这道题

然后我就去写第三题了

现在我来讲一讲思路

首先利润 a [ i ] a[i] a[i]的范围最大是1e19所以必定超long long 所以我们就可以用__int128, long double 高精之类的

然后因为最多可供 a [ 1 ] a[1] a[1]个人选择，因为是选择连续的物品

我们先求出前缀和，先用一个栈记录一下比只选第一个的利润大的点，保持栈中的单调递增

然后从栈顶开始计算，每次更新ans后要减去相应的物品，因为到这个点一定会用到前面的点

贪心思路：

因为所有人都必须吃第一盘菜，

所以 b 1 b_1 b1​就是最大的顾客数

所求的利润只要求一下前缀和然后取最大值就可以了…

AC代码

#include <bits/stdc++.h>
#define ll __int128

using namespace std;
const int maxn=100005;
ll a[maxn],sum[maxn];
int b[maxn];
stack<int> st;
const int INF=0x3f3f3f3f;
__int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
 
void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
int main(){
	int T,n;
	scanf("%d",&T);
	int cas = 1;
	while(T--){
		scanf("%d",&n);
		memset(sum,0,sizeof(sum));
		int ans1 = 0;
		ll ans2 = 0;
		for(int i = 1;i <= n;i++){
			a[i] = read();
			sum[i] = sum[i-1]+a[i];
		}
		int minn = INF;
		for(int i = 1;i <= n;i++){
			scanf("%d",&b[i]);
			minn = min(minn,b[i]);
			b[i] = minn;
		}
		ans1 = b[1];
		st.push(1);
		for(int i = 2;i <= n;i++){
			if(sum[i] > sum[st.top()]){
				st.push(i);
			}
		}
		ll pre = b[st.top()];
		ans2 += (ll)sum[st.top()] * (ll)b[st.top()];
		st.pop();
		while(st.size()){
			if(pre != b[st.top()]){
				ans2 += (ll)sum[st.top()] * (ll)(b[st.top()] - pre);
				pre = b[st.top()];
				st.pop();
			}
			else st.pop();
		}
		printf("Case #%d: %d ",cas++, ans1);
		print(ans2);
		printf("\n");
	}
	return 0;
}

---