//    hdu2430 Beans 单调队列////    题目意思：//    求一个sum%p<=k的max(sum/p)////    结题报告://    技巧，先求出前缀和，并记录前i项对p取余的值记为x，并记下位置pos//    依照先按x从小到大。假设x同样按pos从小到大排序。

这样，问题就转换为 // 求一个最小的pos使得pos到i的值最大。 // // 单调队列里面保持的就是对于当前的i最小的pos值(满足pos到i区间的sum是满足条件的) // 由于数组递增，这样求得的sum一定是最大的,这样就能够了 // // 感悟： // // 这题应该也能够用线段树做，做的话也是以i为端点，查找最小的pos。而这个pos在 // sum[i]%p-k,sum[i]%p之间(由于k>=(sum[i]-sum[pos])%p>0),维护最小值。

待我练练线段树 // 再加上自己更深的理解而单调队列也能实现以i为结尾的区间之前的最小的pos值， // 感觉单调队列实在非常巧妙 #include <cstdio> #include <algorithm> #include <cstring> #include <iostream> typedef long long ll; using namespace std; const int MAX_N = 1e6 + 100; struct node { int pos; int val; }a[MAX_N],deq[MAX_N]; ll f[MAX_N]; int t; int n,p,k; bool cmp(node a,node b){ if(a.val!=b.val) return a.val < b.val; return a.pos < b.pos; } void input(){ cin >> n >> p >> k; f[0] = 0; for (int i=1;i<=n;i++){ cin >> f[i]; f[i] = f[i-1] + f[i]; a[i].val = (int)(f[i]%(ll)p); a[i].pos = i; } sort(a+1,a+n+1,cmp); } void solve(){ int head = 0,tail = 0; ll mx = -1; for (int i=1;i<=n;i++){ while(head < tail && deq[tail-1].pos >= a[i].pos) tail--; deq[tail++] = a[i]; while(head < tail && a[i].val - deq[head].val > k) head++; if (f[a[i].pos]%(ll)p<=k) mx = max(mx,f[a[i].pos]/p); else if (head < tail && deq[head].pos < a[i].pos){ mx = max(mx,(f[a[i].pos] - f[deq[head].pos])/p); } } cout << mx << endl; } int main(){ ios::sync_with_stdio(false); //freopen("1.txt","r",stdin); int t; cin >> t; int kase = 1; while(t--){ input(); cout << "Case " << kase++ << ": "; solve(); } }