題目大意：有n坨豌豆，每坨都有w[i]個，現在要從中選擇連續的若干坨，然後用一個能裝p個豌豆的背包裝豆子，直到剩下的豌豆數量<=p為止，還要求剩下的豌豆數量少於k，問最多能裝多少包。
解題思路：題意很明了，模型也很好抽象。本題就是要選擇連續的一段和為sum，使得max(sum/p) 且sum%p<=k。那麼要怎麼算這個sum呢？這裡就大有文章可做了。
其實這類求區間和的問題很經常是用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艹代碼：
[cpp]
#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 head,tail;
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;
head = 0,tail = 1;
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].in < qu[head].in) head--;
qu[++head] = r[i];
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);
}
}
