[NTUJ] 2789. Graduate Record Examinations
題目連結:http://acm.csie.org/ntujudge/problem.php?id=2789
原本想要用離散化在定義一堆其怪的狀態來做這題,不過越寫越寫不出來。被雷了才知道,原來其實把那堆bit看成一堆線段就好了,那其實退位就是讓目前最低位消失,並在低他一位的地方長出一堆一直到現在這位置,而進位就更不用說了,畢竟原本進位就是均攤$O(1)$了。
原本想要用離散化在定義一堆其怪的狀態來做這題,不過越寫越寫不出來。被雷了才知道,原來其實把那堆bit看成一堆線段就好了,那其實退位就是讓目前最低位消失,並在低他一位的地方長出一堆一直到現在這位置,而進位就更不用說了,畢竟原本進位就是均攤$O(1)$了。
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
vector<PII> work, ans;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int t; cin>>t;
while(t--){
work.clear();
ans.clear();
minHeap<int> pq1, pq2;
int n; cin>>n;
for(int i=0;i<n;i++){
char c;int k;
cin>>c>>k;
if(c=='+') pq1.push(k);
else if(c=='-') pq2.push(k);
}
while(pq1.size()>1){
auto a=pq1.top();pq1.pop();
auto b=pq1.top();pq1.pop();
if(a==b) pq1.push(a+1);
else{
work.PB({a,1});
pq1.push(b);
}
}
if(!pq1.empty()) work.PB({pq1.top(), 1});
while(pq2.size()>1){
auto a=pq2.top();pq2.pop();
auto b=pq2.top();pq2.pop();
if(a==b) pq2.push(a+1);
else{
work.PB({a,0});
pq2.push(b);
}
}
if(!pq2.empty()) work.PB({pq2.top(), 0});
sort(ALL(work), [](PII a, PII b){return a>b;});
for(auto i:work){
if(i.SS == 1) ans.PB({i.FF,i.FF});
else{
int high = ans.back().SS++;
if(ans.back().FF < ans.back().SS) ans.pop_back();
ans.PB({high-1, i.FF});
}
}
int cnt=0;
for(auto i:ans) cnt += i.FF-i.SS+1;
cout<<cnt<<'\n';
}
return 0;
}
留言
張貼留言