普及第五题
题目描述
你有n个立方体，要用它们建造塔。每当两个立方体叠在一起时，上面的立方体必须比下面的立方体小。你必须按照给定的顺序处理立方体。你可以将立方体放在现有的塔上，也可以开始新的塔。请问最少需要多少个塔？
输入格式
从文件towers.in 中读入数据。
第一行包含一个整数n：立方体的数量。接下来一行包含n个整数k1，k2，…，kn：立方体的大小。
输出格式
输出到文件towers.out 中。
输出一个整数：最少需要的塔的数量。
样例
Input 1
5 3 8 2 1 5
Output 1
2
数据范围
1 ≤ n ≤ 2 * 10^5，1 ≤ ki ≤ 10^9
样例解释
对于样例1，可以分别将立方体2和立方体1放在不同的塔上，所以最少需要2个塔。
WA76代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
int n,k[N],l=1,r,mid;
bool check(int x){
priority_queue<int,vector<int>,greater<int> > q;
q.push(k[1]);
for(int i=2;i<=n;i++){
if(k[i]>=q.top()) q.push(k[i]);
else{
q.pop();
q.push(k[i]);
}
}
return q.size()<=x;
}
signed main(){
freopen("towers.in","r",stdin);
freopen("towers.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) cin>>k[i];
r=n;
while(l<r){
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}