[LOJ10181]绿色通道

一看到求什么“最大的最小值”，“最小的最大值”就马上想到二分（还有可能是单调队列）
再仔细看看题目，貌似没什么头绪，但答案似乎存在单调性，果断二分。
答案肯定在0到n范围内。
设$f[i]$为做到第$i$个作业时所需要花的最短时间。
假如我们可以空$k$道题（二分出来的）
$f[i]=min(f[i],f[j]+a[i])$
其中 $ $i-k+1 \le j$

//90分，超时
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=50004;
int n,t;
int a[MAXN],f[MAXN];

bool check(int k){
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=k;i++)f[i]=a[i];
    for(int i=k+1;i<=n;i++){
        for(int j=i-k-1;j<i;j++){
            f[i]=min(f[i],f[j]+a[i]);
        }
    }
    int ans=1<<30;
    for(int i=n-k;i<=n;i++)ans=min(f[i],ans);
    if(ans<=t)return 1;
    return 0;
}

int main(){
    cin>>n>>t;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int l=0,r=n,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

//90分，超时

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN=50004;

int n,t;

int a[MAXN],f[MAXN];

bool check(int k){

memset(f,0x3f,sizeof(f));

f[0]=0;

for(int i=1;i<=k;i++)f[i]=a[i];

for(int i=k+1;i<=n;i++){

for(int j=i-k-1;j<i;j++){

f[i]=min(f[i],f[j]+a[i]);

}

int ans=1<<30;

for(int i=n-k;i<=n;i++)ans=min(f[i],ans);

if(ans<=t)return 1;

return 0;

}

int main(){

cin>>n>>t;

for(int i=1;i<=n;i++)scanf("%d",&a[i]);

int l=0,r=n,ans=0;

while(l<=r){

int mid=(l+r)/2;

if(check(mid))r=mid-1,ans=mid;

else l=mid+1;

}

cout<<ans;

return 0;

}

如果你想要满分，就要减少枚举量，就是减少枚举j的次数。
我们要维护一个区间最小数，可以用线段树来写，我这里采用的是优先队列。
采用优先队列有一个原则，那就是队列里的元素要单调，并且还要有另一个条件限制它们，我比较喜欢叫做“保质期”（因为保质期是不变的但是时间在变）
这个题目单调队列里的元素的保质期就是下标，如果他的下表不满足上面的枚举j的条件，这个元素就“过期”了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int MAXN=50004;
int n,t;
int a[MAXN],f[MAXN];
deque<pair<int,int> >q;

bool check(int k){
    memset(f,0x3f,sizeof(f));
    while(q.size())q.pop_front();
    f[0]=0;
    //q.push_back(make_pair(0,0));加上这句话就不用分开处理
    for(int i=1;i<=k+1;i++){
        f[i]=a[i];
        while(q.size()&&q.back().first>=a[i])q.pop_back();
        q.push_back(make_pair(a[i],i));
    }
    for(int i=k+2;i<=n;i++){
        // cout<<q.front().first<<" "<<q.front().second<<" "<<i-k-1<<endl;
        while(q.size()&&q.front().second<i-k-1)q.pop_front();
        f[i]=min(f[i],q.front().first+a[i]);
        while(q.size()&&q.back().first>=f[i])q.pop_back();
        q.push_back(make_pair(f[i],i));
    }
    int ans=1<<30;
    for(int i=n-k;i<=n;i++)ans=min(f[i],ans);
    if(ans<=t)return 1;
    return 0;
}

int main(){
    cin>>n>>t;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int l=0,r=n,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<deque>

using namespace std;

const int MAXN=50004;

int n,t;

int a[MAXN],f[MAXN];

deque<pair<int,int> >q;

bool check(int k){

memset(f,0x3f,sizeof(f));

while(q.size())q.pop_front();

f[0]=0;

//q.push_back(make_pair(0,0));加上这句话就不用分开处理

for(int i=1;i<=k+1;i++){

f[i]=a[i];

while(q.size()&&q.back().first>=a[i])q.pop_back();

q.push_back(make_pair(a[i],i));

}

for(int i=k+2;i<=n;i++){

// cout<<q.front().first<<" "<<q.front().second<<" "<<i-k-1<<endl;

while(q.size()&&q.front().second<i-k-1)q.pop_front();

f[i]=min(f[i],q.front().first+a[i]);

while(q.size()&&q.back().first>=f[i])q.pop_back();

q.push_back(make_pair(f[i],i));

}

int ans=1<<30;

for(int i=n-k;i<=n;i++)ans=min(f[i],ans);

if(ans<=t)return 1;

return 0;

}

int main(){

cin>>n>>t;

for(int i=1;i<=n;i++)scanf("%d",&a[i]);

int l=0,r=n,ans=0;

while(l<=r){

int mid=(l+r)/2;

if(check(mid))r=mid-1,ans=mid;

else l=mid+1;

}

cout<<ans;

return 0;

}

评论

发送评论编辑评论

评论

发送评论 编辑评论

发送评论编辑评论