跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:22:09

    用连续数组保存两个堆和已支付标记,删除两张账单后惰性清理另一堆;相同面额也按独立编号保存,避免重复支付。缓冲输入和输出减少大数据耗时,保留每天从所有未支付账单选择最小、最大两张的规则。

    #include <bits/stdc++.h>
    using namespace std;
    
    struct FastInput{
        char buffer[1<<16];size_t at=0,length=0;
        int get(){if(at==length){length=fread(buffer,1,sizeof(buffer),stdin);at=0;if(!length)return EOF;}return (unsigned char)buffer[at++];}
        int next(){int c=get();while(c!=EOF&&c<=32)c=get();int x=0;while(c!=EOF&&c>32){x=x*10+c-'0';c=get();}return x;}
    };
    
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    
    FastInput in;int days=in.next(),id=0;
    using Bill=pair<int,int>;
    vector<Bill>lowStorage,highStorage;lowStorage.reserve(days*100);highStorage.reserve(days*100);
    priority_queue<Bill,vector<Bill>,greater<Bill>>low(greater<Bill>(),move(lowStorage));
    priority_queue<Bill,vector<Bill>>high(less<Bill>(),move(highStorage));
    vector<char>paid;paid.reserve(days*100);string output;output.reserve(days*22);
    while(days--){
        int m=in.next();while(m--){int value=in.next();low.push({value,id});high.push({value,id});paid.push_back(false);id++;}
        while(paid[low.top().second])low.pop();Bill a=low.top();low.pop();paid[a.second]=true;
        while(paid[high.top().second])high.pop();Bill b=high.top();high.pop();paid[b.second]=true;
        output+=to_string(a.first)+" "+to_string(b.first)+"\n";
    }
    fwrite(output.data(),1,output.size(),stdout);
    
    return 0;
    }
    
    • 1

    信息

    ID
    4047
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者