快餐店

前言

妙啊，考试的时候我用dp做，速度又慢，代码又长 (所以我打崩了)

算法

贪心 + __int128 高精度

分析

注: n u m [ i ] num[i] num[i]表示第i份菜品最多能端上桌的数量， m i n [ i ] min[i] min[i]表示 m i n n u m [ k ] ( k < i ) min_{num[k]} (k < i) minnum[k]​(k<i)

1.num的初始化

由于在第i盘菜被端上前，之前的菜品是一定会被端走的，所以 n u m [ i ] < = n u m [ k ] ( k < i ) num[i] <= num[k] (k < i) num[i]<=num[k](k<i)，所以 n u m [ i ] = m i n n u m [ k ] ( k < i ) num[i] = min_{num[k]} (k < i) num[i]=minnum[k]​(k<i)

代码

for (int i = 1; i <= n; i++) {_min[i] = Min (_min[i - 1], num[i]);
}

2.贪心求答案

我们首先考虑：

当第i盘菜被端上，对num[k] (k != i) 的影响

(1).k < i

当第k盘菜被端走之前，之前的菜品是一定会被端走的，所以num[k] - 1

(2).k > i

①.num[i + 1] >= num[i]

当第k盘菜端走后，由于 n u m [ i + 1 ] > = n u m [ i ] num[i + 1] >= num[i] num[i+1]>=num[i]， 所以 m i n [ i ] − 1 ( i > k ) min[i] - 1 (i > k) min[i]−1(i>k)

②.num[i + 1] < num[i]

当第k盘菜被端走后，由于 n u m [ i + 1 ] < n u m [ i ] num[i + 1] < num[i] num[i+1]<num[i] ，所以 n u m [ i ] num[i] num[i]的变化对 n u m [ k ] ( k > i ) num[k](k > i) num[k](k>i)无影响

但是！！！
由于 n u m [ j ] − 1 ( j < k ) num[j] - 1 (j < k) num[j]−1(j<k)，所以 n u m [ i ] ( i > k ) num[i] (i > k) num[i](i>k)要么

first.  >=min[k]，则 n u m [ i ] − 1 ( i > k ) num[i] - 1(i > k) num[i]−1(i>k)
second.   < min[k]，同样 n u m [ i ] − 1 ( i > k ) num[i] - 1 (i > k) num[i]−1(i>k)

所以每次选择都会使所有的num[i] - 1，而我们最多选择num[1]次，贪心可得：每次选择利润前缀和最大的是最优解，因为每次端上第i个的利润是 Σ p [ j ] ( j < = i ) \Sigma p[j] (j <= i) Σp[j](j<=i)

代码 (注释好水啊)

高精度懒得打，就用__int128了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL __int128
using namespace std;const int MAXN = 1e5 + 5;
const LL INF = 0x7f7f7f7f7f7f7f;int t, n, now;LL p[MAXN], num[MAXN];
LL _min[MAXN];struct node {int index;LL val;
} pre[MAXN];bool cmp(node x, node y) { return x.val > y.val; }LL Min(LL x, LL y) { return x < y ? x : y; }void read(LL &);
void write(LL);int main() {cin >> t;while (t--) {cin >> n;for (int i = 1; i <= n; i++) read(p[i]);for (int i = 1; i <= n; i++) read(num[i]);_min[0] = INF;for (int i = 1; i <= n; i++) {_min[i] = Min(_min[i - 1], num[i]);pre[i].val = pre[i - 1].val + p[i];pre[i].index = i;}sort(pre + 1, pre + 1 + n, cmp);int sum = 0;  //记录上了多少盘菜__int128 ans = 0;for (int i = 1; i <= n && sum < _min[1];) {int index = pre[i].index;while (_min[index] - sum <= 0) i++, index = pre[i].index;ans += (_min[index] - sum) * pre[i].val;sum = _min[index];//            printf ("i = %d, sum = %d\n", i, sum);}//        printf ("Case #%d: %lld %lld\n", ++now, _min[1], ans);printf("Case #%d: ", ++now);write(_min[1]);cout << " ";write(ans);cout << endl;//        cerr << now << " " << _min[1] << " " << ans << endl;}return 0;
}void read(LL &x) {x = 0;int f = 1;char s = getchar();while (s < '0' || s > '9') {if (s == '-') {f = -1;}s = getchar();}while (s >= '0' && s <= '9') {x = (x << 3) + (x << 1) + s - 48;s = getchar();}x *= f;
}void write(LL x) {if (x < 0)x = -x, putchar('-');if (x > 9)write(x / 10);putchar(x % 10 + '0');
}