栈

由于牛奶只喝最新鲜的，符合先进先出的特征，使用栈来维护。

每次在栈中加入新牛奶，然后计算，对于接下来的若干天（由下次向栈中加入牛奶的时间计算得到的天数），目前的栈状态能够满足多少天的牛奶需求。

具体地，计算无视过期限制的情况下栈顶的牛奶够喝多少天，以及栈顶牛奶的过期时间，利用这两个信息计算当前栈顶对答案的贡献之后修改栈顶。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=1'000'000'000'000'000ll;
struct Milk{long long d,w;}s[100'005];
long long ans;
int n,m,k;
void solution(){
    cin>>n>>m>>k,ans=0ll;
    for(int i=1;i<=n;i++) cin>>s[i].d>>s[i].w;
    s[n+1].d=inf,s[n+1].w=0ll;
    vector<Milk> v;
    for(int i=1;i<=n;i++){
        long long resday=s[i+1].d-s[i].d;//下一次加奶前还剩多少天
        long long nxtned=0ll;//需要的零头
        v.push_back(s[i]);
        while(!v.empty()&&resday!=0ll){
            long long lim=v.back().d+k-1;//保质期
            if(lim<s[i+1].d-resday){//过期
                v.clear();
                continue;
            }
            if(nxtned!=0ll){//处理零头
                long long red=min(nxtned,v.back().w);
                nxtned-=red,v.back().w-=red;
                if(nxtned==0ll) --resday,++ans;//零头用完了
                if(v.back().w==0ll){//牛奶喝完力
                    v.pop_back();
                    continue;
                }
            }
            long long drink=v.back().w/m;//牛奶的量还能喝几天
            long long good=lim-(s[i+1].d-resday)+1;//牛奶还有几天过期
            long long add=min(min(drink,good),resday);//真能喝几天
            ans+=add,resday-=add,v.back().w-=add*m;
            if(resday!=0ll&&add<good&&v.back().w!=0ll){//没过期还有零头
                nxtned=m-v.back().w;
                v.pop_back();
            }
            if(v.back().w==0ll) v.pop_back();
        }
    }
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}