| K | Kabaleo Lite |
The restaurant serves n kinds of food, numbered from 1 to n. The profit for the i-th kind of food is aia_iai. Profit may be negative because it uses expensive ingredients. On the first day, Apollo prepared bib_ibi dishes of the i-th kind of food.
The peculiarity of Apollo's restaurant is the procedure of ordering food. For each visitor Apollo himself chooses a set of dishes that this visitor will receive. When doing so, Apollo is guided by the following rules:
- every visitor should receive at least one dish.
- each visitor should receive continuous kinds of food started from the first food. And the visitor will receive exactly 1 dish for each kind of food. For example, a visitor may receive 1 dish of the 1st kind of food, 1 dish of the 2nd kind of food, 1 dish of the 3rd kind of food.
输入描述:
The first line of the input gives the number of test case, T\mathbf{T}T (1≤T≤101 \leq \mathbf{T} \leq 101≤T≤10). T\mathbf{T}T test cases follow.
Each test case begins with a line containing one integers n (1≤n≤1051 \le n \le 10^51≤n≤105), representing the number of different kinds of food.
The second line contains n space-separated numbers aia_iai (−109≤ai≤109-10^9 \le a_i \le 10^9−109≤ai≤109), where aia_iai denotes the profit of one dish of the i-th kind.
The third line contains n space-separated numbers bib_ibi (1≤bi≤1051 \le b_i \le 10^51≤bi≤105), where bib_ibi denotes the number of the i-th kind of dishes.
输出描述:
For each test case, output one line containing ‘‘Case #x: y z′′``Case\ \#x:\ y\ z''‘‘Case #x: y z′′, where x is the test case number (starting from 1), y is the maximum number of visitors, and z is the maximum possible profits.示例1
输入
复制2 3 2 -1 3 3 2 1 4 3 -2 3 -1 4 2 1 2
输出
复制Case #1: 3 8 Case #2: 4 13
说明
For test case 1, the maximum number of visitors is 3, one of a possible solution is:
The first visitor received food 1, the profit is 2.
The second visitor received food 1, the profit is 2.
The third visitor received food 1 + food 2 + food 3, the profit is 2 + (-1) + 3.
题目大意：
给出每种菜品的利润以及碟数，要求我们给每个客人至少一碟菜，要求从1号菜品开始给，给的菜品的号码是连续的，每个客人同号码的菜都只能给一碟。求能招待客人的最大数量以及在客人最多的情况下能获得的最大利润。
思路：
1.首先，因为要求从1号菜品开始给，所以能招待的客人的最大数量就是1号菜品的碟数。
2.用结构体记录1-x号菜品各一碟可以获得的利润以及x的位置，后续按照利润从大到小的顺序对结构体进行排序。
3.给客人的菜一定是1-x各一盘这种情况，可以用一个time数组对能够上几次1-x的菜进行计数，time[x]即1-x中b[x]的最小值。、
4.最关键的一步。核心代码就是 ans=ans+e[j].sum*(time[e[j].loc]-nowt);
为啥是time[e[j].loc]-nowt呢.举个例子，8 6 7 4 5 3 假设time[e[j].loc]=3那么则要把改系列的菜都上完，然后寻找下一次的，得到time[e[j].loc]=4，这个时候就需要time[e[j].loc]-nowt（上一次上菜的数量）用当前菜的数量的最小最减去上一次上菜的数量的就是这次的上菜数量了。因为保证每次选择到的那个系列的菜都是上完的，所以不需要上一次菜把所有的time[]数组进行处理。例如：假设数量是4的已经上完啦，那么我前面的菜肯定也花费了4个，我们直接用6-4就可以得到这次能上多少菜了。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct noid
{
int loc;//取得当前利润的位置
long long sum;//1-x菜各一碟利润总和
} e[100005];
bool cmp(struct noid a,struct noid b)
{
return a.sum>b.sum;
}
//输入
inline __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;
}
//输出
inline void print(__int128 x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
print(x/10);
putchar(x%10+'0');
}
int main()
{
int i,j,t,n,k,now,nowt;
__int128 a[100005],b[100005],time[100005],ans;
scanf("%d",&t);
for(i=1; i<=t; i++)
{
ans=0;
scanf("%d",&n);
e[0].sum=0;
for(j=1; j<=n; j++)
{
a[j]=read();
e[j].sum=e[j-1].sum+a[j];
e[j].loc=j;
}
for(j=1; j<=n; j++)
{
b[j]=read();
if(j==1)
time[1]=b[1];
if(j>1)
time[j]=min(time[j-1],b[j]);//求1-j菜品数量的最小值
}
sort(e+1,e+1+n,cmp);//对利润进行排序
nowt=0;
now=100005;
for(j=1; j<=n; j++)
{
if(e[j].loc>=now)//因为now前面的菜品一定会出现部分空缺，位置在now后面上不了菜
continue;
ans=ans+e[j].sum*(time[e[j].loc]-nowt);
int cnt=e[j].loc;
if(cnt<=now)
now=e[j].loc;//记录目前的位置
nowt=time[e[j].loc];//记录当前1号菜品被消耗的次数
}
printf("Case #%d: %lld ",i,b[1]);
print(ans);
printf("\n");
}
return 0;
}
View Code