Hdu 2430 Beans (数据结构_单调队列)
题目大意：有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);
}
}
