[POJ 3245] | Eurce's Blog

单调队列 + 二分 + DP

题意：输入为n对数字(ai,bi)，以及m，需要将这n对数字按原始顺序划分为p组，需要满足：（1）前一组的各bi都比后一组的各ai大；（2）各组中最大的ai的和小于等于m。在该条件下进行的划分，将各组bi求和，取其中的最大值。求解目标是最小化该最大值。

非常拗口的题意……但仔细分析之后可以发现条件（1）中规定了n对数之间的哪些位置可以进行划分，而且这些划分位置之间是相互独立的，也即某个位置实际进行划分之后，不影响其他位置的可划分性。这里可以利用单调队列，边遍历数组边记录a的剩余最大值和b的累计最小值来记录各个可划分的位置，处理的时间是O(n)的。

随后分析求解目标，可以得到最大值的存在性是单调的，因此可以二分最大分组b值和，每次判断是否能满足条件（2）。

对条件（2）的判断，可以用DP来实现，对于每个可行的划分位置，计算满足二分值的划分范围内最大a值的累计最小值。这里同样可以利用单调队列作优化。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long

ll n,m;
ll a[50001],b[50001],c[50001],mxa[50001],sb[50001],cl;
ll qa[50001],qb[50001],qah,qat,qbh,qbt,mxb,smb;
ll dp[50001];

void push(ll d[],ll di)
{
    if(d==a)
    {
        while(qat>qah&&d[di]>=d[qa[qat-1]])
            qat--;
        qa[qat++]=di;
    }
    else
    {
        while(qbt>qbh&&d[di]<=d[qb[qbt-1]])
            qbt--;
        qb[qbt++]=di;
    }
}

void pop(ll d[],ll di)
{
    if(d==a)
    {
        while(qah<qat&&qa[qah]<=di)
            qah++;
    }
    else
    {
        while(qbh<qbt&&qb[qbh]<=di)
            qbh++;
    }
}

ll front(ll d[])
{
    return d==a?a[qa[qah]]:b[qb[qbh]];
}

void init()
{
    ll i,j,k,l;
    mxb=smb=cl=0;
    c[cl++]=0;
    memset(mxa,0,sizeof mxa);
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",a+i,b+i);
        mxb=max(mxb,b[i]);
        smb+=b[i];
    }
    for(i=1;i<=n;i++)
        sb[i]=sb[i-1]+b[i];
    qah=qat=qbh=qbt=0;
    for(i=1;i<=n;i++)
        push(a,i);
    mxa[1]=a[1];
    for(i=1;i<n;i++)
    {
        push(b,i);
        pop(a,i);
        if(front(b)>front(a))
        {
            c[cl++]=i;
            mxa[i+1]=a[i+1];
        }
        else
            mxa[i+1]=max(mxa[i],a[i+1]);
    }
    memcpy(a,mxa,sizeof a);
    c[cl++]=n;
}

bool chk(ll bm)
{
    ll i,j,k,l,lk;
    memset(dp,127,sizeof dp);
    dp[0]=0;
    for(l=k=0;l<cl;l++)
    {
        if(dp[c[l]]>m)
            continue;
        for(;k<cl&&sb[c[k]]-sb[c[l]]<=bm;k++);
        if(k==l)
            return 0;
        k--;
        qah=qat=0;
        for(lk=l+1;lk<=k;lk++)
        {
            push(a,c[lk]);
            dp[c[lk]]=min(dp[c[lk]],dp[c[l]]+front(a));
        }
    }
    if(dp[n]<=m)
        return 1;
    else
        return 0;
}

void solve()
{
    ll l,h,mid;
    for(l=mxb,h=smb;l<h;)
    {
        mid=l+h>>1;
        if(chk(mid))
            h=mid;
        else
            l=mid+1;
    }
    printf("%lld\n",l);
}

int main()
{
    while(~scanf("%lld%lld",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

ll n,m;

ll a[50001],b[50001],c[50001],mxa[50001],sb[50001],cl;

ll qa[50001],qb[50001],qah,qat,qbh,qbt,mxb,smb;

ll dp[50001];

void push(ll d[],ll di)

{

if(d==a)

{

while(qat>qah&&d[di]>=d[qa[qat-1]])

qat--;

qa[qat++]=di;

}

else

{

while(qbt>qbh&&d[di]<=d[qb[qbt-1]])

qbt--;

qb[qbt++]=di;

}

void pop(ll d[],ll di)

{

if(d==a)

{

while(qah<qat&&qa[qah]<=di)

qah++;

}

else

{

while(qbh<qbt&&qb[qbh]<=di)

qbh++;

}

ll front(ll d[])

{

return d==a?a[qa[qah]]:b[qb[qbh]];

}

void init()

{

ll i,j,k,l;

mxb=smb=cl=0;

c[cl++]=0;

memset(mxa,0,sizeof mxa);

for(i=1;i<=n;i++)

{

scanf("%lld%lld",a+i,b+i);

mxb=max(mxb,b[i]);

smb+=b[i];

}

for(i=1;i<=n;i++)

sb[i]=sb[i-1]+b[i];

qah=qat=qbh=qbt=0;

for(i=1;i<=n;i++)

push(a,i);

mxa[1]=a[1];

for(i=1;i<n;i++)

{

push(b,i);

pop(a,i);

if(front(b)>front(a))

{

c[cl++]=i;

mxa[i+1]=a[i+1];

}

else

mxa[i+1]=max(mxa[i],a[i+1]);

}

memcpy(a,mxa,sizeof a);

c[cl++]=n;

}

bool chk(ll bm)

{

ll i,j,k,l,lk;

memset(dp,127,sizeof dp);

dp[0]=0;

for(l=k=0;l<cl;l++)

{

if(dp[c[l]]>m)

continue;

for(;k<cl&&sb[c[k]]-sb[c[l]]<=bm;k++);

if(k==l)

return 0;

k--;

qah=qat=0;

for(lk=l+1;lk<=k;lk++)

{

push(a,c[lk]);

dp[c[lk]]=min(dp[c[lk]],dp[c[l]]+front(a));

}

if(dp[n]<=m)

return 1;

else

return 0;

}

void solve()

{

ll l,h,mid;

for(l=mxb,h=smb;l<h;)

{

mid=l+h>>1;

if(chk(mid))

h=mid;

else

l=mid+1;

}

printf("%lld\n",l);

}

int main()

{

while(~scanf("%lld%lld",&n,&m))

{

init();

solve();

}

return 0;

}

但即使这样，极端情况下时间复杂度其实是要O(n^2*lgk)的。能过题目，大概也是数据不够强。

相关类型的题目，推荐这篇文章，总结得很好。

<也啰嗦一点自己的想法>
最近几天研究的单调队列确实是非常独特的数据结构，稍作小结的话，可以发现常用的维护区间信息的数据结构好多，包括：线段树，树状数组，用于离线rmq的st算法，以及现在学到的单调队列。如果要进行比较的话，大致如下：

线段树：应该算是最灵活的数据结构。更新、查询信息可以针对点，也可以针对区间，每次操作时间复杂度是O(lgn)。但实现起来细节较多。

树状数组：轻便的数据结构，易于扩展到多维。更新只能针对点，查询的是区间，每次操作都是O(lgn)。相对于线段树，缺点是灵活性较差，难以应用于不同类型的题目。

st算法：不同于以上两个在线算法，st是离线的。首先O(nlgn)地构造一个保存预处理信息的数组，以后每次查询信息的时间复杂度都是O(1)的。该算法几乎算是“模块化”的，因此很易与其他算法结合使用。典型应用是后缀数组。

单调队列：需要在遍历数组的同时，动态地维护当前有效区间内的信息。仅适用于已知区间长度限制的情况，但时间复杂度非常优秀，达到O(n)。

如果可以一直这样做题下去的话…………还能学到多少呢？
<⁄啰嗦完毕>

最后，快放假了，也预祝各位新年愉快。