Skip to content

优先队列/二叉堆

P7913

直接用堆优化模拟。

建两个堆，分别维护\(lq:\)出发时间+占据廊桥编号，和\(wq:\)空闲廊桥编号。

每次将小于\(tmp[i].l\)的廊桥从\(lq\)种释放出来，加入\(wq\)中。

如果没有空闲廊桥直接跳过(远区情况)

否则就将它加到编号最小的廊桥\(pos\)中，并将这个廊桥从\(wq\)中去除，加入\(lq\). make_pair(tmp[i].r,pos);

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> pii;
struct node{
    int l,r;
}s[N],t[N];
int n,m1,m2,ans;
int f[N],g[N];
bool cmp(node a,node b){return a.l<b.l;}

void cal(node* tmp,int m,int* res){
    priority_queue<pii, vector<pii> ,greater<pii> > lq;
    priority_queue<int, vector<int> ,greater<int> > wq;
    for(int i=1;i<=n;++i)wq.push(i);
    for(int i=1;i<=m;++i){
        while(!lq.empty() && tmp[i].l>=lq.top().first){
            wq.push(lq.top().second);
            lq.pop();
        }
        if(wq.empty())continue;
        int pos=wq.top();wq.pop();
        res[pos]++;

        lq.push(make_pair(tmp[i].r,pos));
    }
    for(int i=1;i<=n;++i)res[i]+=res[i-1];
}

int main(){
    scanf("%d%d%d",&n,&m1,&m2);
    for(int i=1;i<=m1;++i)scanf("%d%d",&s[i].l,&s[i].r);    
    for(int i=1;i<=m2;++i)scanf("%d%d",&t[i].l,&t[i].r);
    sort(s+1,s+m1+1,cmp);
    sort(t+1,t+m2+1,cmp);

    cal(s,m1,f);
    cal(t,m2,g);
    ans=0;
    for(int i=0;i<=n;++i)ans=max(ans,f[i]+g[n-i]);

    printf("%d",ans);
    return 0;
}

P1631

~~我是SB~~ 对于a与b数组由下列不等式关系： 

a[1]+b[1]<=a[1]+b[2]<=...<=a[1]+b[n]
a[2]+b[1]<=a[2]+b[2]<=...<=a[2]+b[n]
.
.
.
a[n]+b[1]<=a[n]+b[2]<=...<=a[n]+b[n]
那么就将n个不等式的第一个数推进堆里，每次弹出最小的，并将它对应的不等式中它的下一个数入堆即可。 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N],b[N],c[N];
int n;
struct node{
    int i,j,s;
    node(int x,int y,int z){
        i=x;
        j=y;
        s=z;
    }
    bool operator <(const node &a)const{
        return a.s<s;
    }
};
void solve(){
    priority_queue<node> q;
    for(int i=1;i<=n;++i){
        int tmp=a[1]+b[i];
        q.push(node(1,i,tmp));
    }
    int cnt=0;
    for(int i=1;i<=n;++i){
        c[++cnt]=q.top().s;
        int x1=q.top().i,y1=q.top().j;
        q.pop();
        int z1=a[x1+1]+b[y1];
        q.push(node(x1+1,y1,z1)); 
    }
    for(int i=1;i<=n;++i)printf("%d ",c[i]); 
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)scanf("%d",&b[i]);
    solve();
    return 0;
}

P2827

这题用堆或优先队列"只能"拿85pts~~这对于考试就够了，要什么正解~~

正解是"看出"它的单调性。

  • \(如果a>b,a分成a_1,a_2,b分成b_1,b_2,则a_1>b_1,a_2>b_2.\)

其实这也很好理解，所以证明略。

那么我们就可以开三个数组模拟队列，一个存\(a\),一个存\(a_1\),一个存\(a_2\).

UVA11997

与上一题类似，只不过变成了\(k\)个数组，此时一行一行做即可。

问题是，当前回合抛弃的大数会不会在下回合用到？

考虑反证，假设\(k+1\)大的数下回合用到，此时前\(k\)大的数加下回合最小的数一定比\(k+1\)大的数加下回合最小的数小，即一定存在至少\(k\)个比他小的数，所以第\(k+1\)大的数就可以忽略，每次只需要维护\(k\)个数即可。

#include<iostream>
#include<cstdio> 
#include<cstring>
#include<queue>
#include<algorithm>
#define int long long 
using namespace std;
const int N=810;
int a[N][N];
int k;
struct node{
    int s,b;
    node(int ss,int bb){
        s=ss,b=bb;
    }
    bool operator <(const node &x)const{
        return x.s<s;
    }
};
bool cmp(int a,int b){return a<b;}
void merge(int j){
    priority_queue<node> q;
    for(int i=1;i<=k;++i)q.push(node(a[1][i]+a[j][1],1));
    for(int i=1;i<=k;++i){
        node tmp=q.top();q.pop();
        int s=tmp.s,b=tmp.b;
        a[1][i]=s;
        if(b<k)q.push(node(s-a[j][b]+a[j][b+1],b+1));
    }
}
signed main(){
    //freopen("UVA11997.txt","r",stdin);
    while(scanf("%lld",&k)!=EOF){
        memset(a,0,sizeof a);
        for(int i=1;i<=k;++i){
            for(int j=1;j<=k;++j)scanf("%lld",&a[i][j]);
            sort(a[i]+1,a[i]+k+1,cmp);
        }
        for(int i=2;i<=k;++i)merge(i);
        printf("%lld",a[1][1]);
        for(int i=2;i<=k;++i)printf(" %lld",a[1][i]);
        printf("\n");
    }
    return 0;
}

P8179

16pts:

直接暴力\(dp\).

设\(g[i]\)表示考虑了前\(i\)圈是的最小贡献。将换台的时间加在第一圈的贡献上面，相当于去掉了换胎的操作。

则转移方程：

\(f[i]=\min_{j=0}^i(f[i],f[i-j]+c(o,j))\),\(o\)表示当前考虑的是哪一个轮子。

复杂度\(O(nm^2)\).

13pts:

对于\(t=0\)的情况其实就相当于给你\(n\)个长度为\(m\)的不等式，让你合并出前\(m\)个最小的值。直接用堆+贪心维护即可。

正解:

我们不能用堆维护的原因在于序列不单调，这是由换胎时间引起的，而\(dp\)不会受影响。

注意到一个轮胎最多在使用\(25\)圈后，使用当前轮胎的时间就会大于换胎的时间加第一圈所用时间，序列又一次变得单调。

因此我们可以将每个轮胎前\(25\)圈做\(dp\)，后面用堆维护。

并不会出现"断层"，即前面\(dp\)没取到的圈数，该轮胎在后面堆中取到了，因为前面的一定比后面的更优，取最优解时会自动淘汰。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long 
using namespace std;
const int N=510,M=2e5+10,INF=2e18,T=25;
int n,m,t,s;
int a[N],b[N],c[N];
int g[M],h[M],f[N][T+T];
inline int d(int i,int j){return a[i]+(j-1)*(j-1)*b[i];}
struct node{
    int n,m,val;
    bool operator <(const node &x)const{
        return x.val<val;
    }
    node(int _n,int _m,int _val){
        n=_n,m=_m,val=_val;
    }
};
void init(){
    for(int i=1;i<=n;++i){
        f[i][0]=t;
        for(int j=1;j<=T;++j)
            f[i][j]=f[i][j-1]+d(i,j);
    }
}
void heap_greedy(){
    priority_queue<node> q;
    for(int i=1;i<=n;++i)q.push(node(i,T+1,d(i,T+1)));  
    for(int i=1;i<=m;++i){
        node tmp=q.top();q.pop();
        h[i]=h[i-1]+tmp.val;
        q.push(node(tmp.n,tmp.m+1,d(tmp.n,tmp.m+1)));
    }
}
void dp(){
    memset(g,0x3f,sizeof g);
    g[0]=0;
    for(int o=1;o<=n;++o){
        s=min(s+T,m);
        for(int j=s;j>=0;--j)
            for(int k=min(j,T);k>=0;--k)
                g[j]=min(g[j],g[j-k]+f[o][k]);  
    }
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&t);
    for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i],&b[i]);
    init();
    dp();
    heap_greedy();
    int ans=INF;
    for(int i=1;i<=min(m,s);++i) ans=min(ans,g[i]+h[m-i]);
    printf("%lld",ans-t);
    return 0;
}