B-艰难睡眠

分析

1. 最开始看到题目时我是完全没有一点思路的，直到题面更新发现必须睡连续的时间。。。。再考虑到一天最多有2000分钟，k也是固定的，很自然的就可以想到可以枚举在哪段时间里睡觉，然后将所有人的吵闹时间移动至这段时间之外即可。
2. 然后考虑怎么优化。发现当我确定了睡眠的时间段后，每个人可选的开始吵闹的时间是一段连续的区间。显然假设我在[l,r]这段时间里睡觉，第i个人吵闹开始时间可选区间的li=r+1。因为可能会吵到第二天，所以ri+bi-1<m+l，我们要求的就是区间最小值，显然可以用单调队列维护。
3. 同时，我们发现如果一个人的可选吵闹区间为空，那么就没有结果。即当存在k+bi>m时无解。

注意事项

其实这题也没太多特别需要注意的地方吧，实现也比较简单，只要记得判无解，同时将它看做一个环，跑两倍大小来处理第二天的情况就可以了。

Code

#include<bits/stdc++.h>
#define M 5005
namespace io 
{ 
const int L = (1 << 21) + 1; 
char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, st[55]; 
int f, tp; 
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++) 
inline void gi(int& x) { //get    
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc())         if (c == '-') f = -1;     for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);     x *= f; } };  // namespace io 
using io::gi;
using namespace std;
int n,m,k;
int ans,a[M],b[M],c[M][4005],r[M];
bool flag;
int q[M][4005],tail[M],head[M];
int main()
{
    int i,j;
//    freopen("2.in","r",stdin);
//    cout<<sizeof(q)+sizeof(c)<<endl;
    gi(n);gi(m);gi(k);
    for(i=1;i<=n;i++)
    {
        gi(a[i]);gi(b[i]);
        if(m-b[i]<k)flag=1;
    }                          //判断是否无解
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)gi(c[i][j]);
        for(j=m+1;j<=2*m;j++)c[i][j]=c[i][j-m];
    //    for(j=1;j<=m*2;j++)cout<<c[i][j]<<" ";cout<<endl;
    }
    if(flag)
    {
        puts("-1");
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        head[i]=1;tail[i]=0;
        for(j=k+1;j<=m;j++)
        {
            if(j+b[i]-1>m)break;r[i]=j;
            while(tail[i]>=head[i]&&c[i][q[i][tail[i]]]>=c[i][j])tail[i]--;
            q[i][++tail[i]]=j;
        }
        ans+=c[i][q[i][head[i]]];
    //    cout<<i<<" ee "<<c[i][q[i][head[i]]]<<" tim "<<k+1<<" "<<r[i]<<endl;
    }                                 //先做睡[1,k]的情况，后面的每次ri只会增加1
//    cout<<ans<<endl;
    for(i=k+1;i<=m+k;i++)
    {
        int res=0;
        for(j=1;j<=n;j++)
        {
            r[j]++;
            while(tail[j]>=head[j]&&c[j][q[j][tail[j]]]>=c[j][r[j]])tail[j]--;
            q[j][++tail[j]]=r[j];
            while(q[j][head[j]]<=i)head[j]++;
            res+=c[j][q[j][head[j]]];
    //        cout<<j<<" ee "<<c[j][q[j][head[j]]]<<" tim "<<i+1<<" "<<r[j]<<endl;
        }
        ans=min(ans,res);
    //    cout<<ans<<endl;
    }                                  //主体部分，单调队列求解
    printf("%d",ans);
    return 0;
}