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