2014
01-26

# Beans

Mr. Pote’s shop sells beans now. He has N bags of beans in his warehouse, and he has numbered them with 1, 2, …, N according to their expired dates. The i-th bag contains Wi units of beans. For selling at retail makes only a little profit, Mr. Pote want to pack beans in small packets with certain size and sell them in packets. Here comes his packing way:
Suppose the size of the packet is P units. Firstly, Mr. Pote selects some bags (at least one) of beans with consecutive number in his warehouse. Then he takes out the beans from all selected bags, and puts them together on the desktop. To pack the beans, he take P units of beans from desktop and fill in a new packet each time, until the beans left are less than P units. Finally the beans left on the desktop are eaten by a lucky dog.
Mr. Pote doesn’t want the dog eat too many beans, so he prefers to solutions that resulting no more than K units of beans eaten by the dog. Moreover, he also wants to pack as many packets as possible. Could you tell him how many packets he can pack at most without breaking his preference?

On the first line of input, there is a single positive integer T <= 20 specifying the number of test cases to follow.
Each test case contains two lines.
There are three integers in the first line, N, P, K as described above. (0 < N, P < 1000001, 0 <= K < P)
Next follow a line with N integers W1, W2, …, WN. The i-th integers describes the amount of beans in the bags numbered i. (0 <= Wi < 32768)
Numbers are separated by spaces.

On the first line of input, there is a single positive integer T <= 20 specifying the number of test cases to follow.
Each test case contains two lines.
There are three integers in the first line, N, P, K as described above. (0 < N, P < 1000001, 0 <= K < P)
Next follow a line with N integers W1, W2, …, WN. The i-th integers describes the amount of beans in the bags numbered i. (0 <= Wi < 32768)
Numbers are separated by spaces.

3
10 20 10
0 3 1 8 19 39 2 9 1 8
3 100 10
32 34 23
1 5 3
1

Case 1: 4
Case 2: -1
Case 3: 0

其实这类求区间和的问题很经常是用sum[i]- sum[j-1]这种方式来表达的，我们设sum[i]表示0到i坨豌豆的总数量，那么上面的sum就是sum[i]-sum[j-1]。从而得到一个式子,max(sum[i]-sum[j]) (j < i && (sum[i]-sum[j])%p<=k)，表示以i为区间尾，因为豌豆数量非负数，那我们向前找个最小的下标使得差最小且符合条件即可。

我们设sum[i]为x，sum[j]为y，那么上式变成0<=(x-y)%p<=k且x-y最大，约束条件是x大等于y，我们要利用这些条件快速地找到x对应的那个最小的y。

0<=(x-y)%p<=k  –>  0<=(x%p – y%p + p) % p<=k

如果x%p >= y%p，那么x%p-k<=y%p<=x%p，我们就可以根据x%p来定位y%p.

如果x%p < y%p,那么我们可以换个角度想，在以y结尾的时候就会有上面的情况。

那问题就剩下一个了，如果根据x%p来快速定位y%p。写法有多种，用线段树和树状数组都可以写，但我用线性的单调队列来写，时间78ms，是提交记录的第二名。

我先将每个和对p取余得到一个余数r数组，然后按余数大小优先位置其次的顺序排序。排完序之后就可以根据ri – k <= rj <= ri来往前找那个最小的j。遍历数组r，因为r是有序的，我用单调队列储存r小于当前的最小下标。关于单调队列，我就不多说了，百度google去。最后更新答案即可。

总复杂度还是(nlogn)，主要用于排序。

20
2 19 3
17 3
Out:Case 1: 1

2 19 1

17 3
Out:Case 2: 1

2 19 3

17 6
Out:Case 3: -1

10 20 10

0 3 1 8 19 39 2 9 1 8

Out:Case 4: 4

3 100 10

32 34 23
Out:Case 5: -1

1 5 3

5
Out:Case 6: 1

5 15 4

7 8 3 10 10
Out:Case 7: 2

C艹代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 1000010
#define max(a,b) (a)>(b)?(a):(b)

struct node {

int x,in;
}r[MAX],qu[MAX];
__int64 sum[MAX],ans;
int n,p,k,mmin[MAX];

int cmp(node a,node b) {

if (a.x == b.x) return a.in < b.in;
else return a.x < b.x;
}
void Solve_AC() {

int i,j;

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

if (tail > head) mmin[r[i].in] = -1;
else mmin[r[i].in] = qu[tail].in;

while (tail <= head && r[i + 1].x - qu[tail].x > k)
tail++;
}

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

if (sum[i] % p <= k) ans = max(ans,sum[i] / p);
if (mmin[i] == -1 || mmin[i] >= i) continue;
ans = max(ans,(sum[i] - sum[mmin[i]]) / p);
}
}

int main()
{
int i,j,t,cas = 0;

scanf("%d",&t);
while (t--) {

scanf("%d%d%d",&n,&p,&k);
for (i = 1; i <= n; ++i) {

scanf("%d",&sum[i]);
r[i].in = i;
sum[i] +=  sum[i-1];
r[i].x = sum[i] % p;
}

sort(r+1,r+1+n,cmp);
ans = -1,Solve_AC();
printf("Case %d: %I64d\n",++cas,ans);
}
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge