#131: 為什麼我前面的側資都30出(ms)最後一個卻超時阿


abc0979999412@gmail.com (白兔)

School : No School
ID : 2032
IP address : [203.203.86.4]
Last Login :
2022-09-23 10:13:48
d060. Q-4-19. 五嶽盟主的會議場所 -- AP325 | From: [203.203.86.4] | Post Date : 2022-09-23 10:28

附上我的程式碼
有人可以分享解法嗎

#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct guild{
    int m,s,t;
};
bool cmp(guild a,guild b){
    return a.s<b.s;
}
struct cmp2{
    bool operator()(guild a, guild b){
        return a.t<b.t;//需要反向定義
    }
};
guild g[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,mx=0;
    priority_queue<guild,vector<guild>,cmp2> pq;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>g[i].m>>g[i].s>>g[i].t;
    sort(g,g+n,cmp);
    for(int i=0,mb;i<n;i++){//mb=maxbuffer
        mb=0;
        priority_queue<guild,vector<guild>,cmp2> buffer;
        mb+=g[i].m;
        while(!pq.empty()){
            guild top;
            top=pq.top();
            if(g[i].s<=top.t){
                mb+=top.m;
            }else{
                break;
            }
            buffer.push(top);
            pq.pop();
        }
        mx=max(mx,mb);
        pq=buffer;
        pq.push(g[i]);
    }
    cout<<mx;
    return 0;
}
 
#136: Re:為什麼我前面的側資都30出(ms)最後一個卻超時阿


mses010108@gmail.com (Owen Lin)

School : 明道
ID : 2655
IP address : [61.223.86.129]
Last Login :
2023-01-11 22:01:13
d060. Q-4-19. 五嶽盟主的會議場所 -- AP325 | From: [61.223.86.129] | Post Date : 2023-01-13 11:50

附上我的程式碼
有人可以分享解法嗎

#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct guild{
    int m,s,t;
};
bool cmp(guild a,guild b){
    return a.s<b.s;
}
struct cmp2{
    bool operator()(guild a, guild b){
        return a.t<b.t;//需要反向定義
    }
};
guild g[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,mx=0;
    priority_queue<guild,vector,cmp2> pq;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>g[i].m>>g[i].s>>g[i].t;
    sort(g,g+n,cmp);
    for(int i=0,mb;i<n;i++){//mb=maxbuffer
        mb=0;
        priority_queue<guild,vector,cmp2> buffer;
        mb+=g[i].m;
        while(!pq.empty()){
            guild top;
            top=pq.top();
            if(g[i].s<=top.t){
                mb+=top.m;
            }else{
                break;
            }
            buffer.push(top);
            pq.pop();
        }
        mx=max(mx,mb);
        pq=buffer;
        pq.push(g[i]);
    }
    cout<<mx;
    return 0;
}

因為你的while迴圈是用+的,導致重複的數值會算很多次,而這樣worstcase會是O((N^2)*log(N)),可以考慮試試用減的。

 
ZeroJudge Forum