注意
用优先队列维护数组值及下标时
若之后修改了数组中的值,则一定要记得向队列中插入新的 {值, 下标}
法一:堆+暴力
蓝桥官网能过100%的数据,但ACWing不行
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PII;
const int N=2e5+10;
int n;
LL h[N];
priority_queue<PII> q;
int main(){
cin >> n;
for(int i=0;i<n;i++){
scanf("%lld",&h[i]);
q.push({h[i],i});
}
int res=0;
while(q.size()){
PII t=q.top();
q.pop();
if(t.first==1) continue;
if(t.first!=h[t.second]){
t.first=h[t.second];
q.push(t);
}else{
res++;
int i=t.second, j=t.second;
while(j<n && h[j]==h[j+1]) j++;
while(i>=0 && h[i]==h[i-1]) i--;
LL tmp=sqrtl(h[i]/2+1);
for(int k=i;k<=j;k++) h[k]=tmp;
q.push({tmp,i});
}
}
cout << res << endl;
return 0;
}
法二:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=2e5+10,M=10;
int n;
LL h[N][M];
LL stk[M];
int main(){
cin >> n;
int res=0;
for(int i=0;i<n;i++){
LL x;
int top=0;
scanf("%lld",&x);
while(x>1){
stk[++top]=x;
x=sqrtl(x/2+1);
}
res+=top;
for(int j=top,k=0;j>0;j--,k++) h[i][k]=stk[j];
}
for(int i=0;i<n;i++){
for(int j=0;h[i][j];j++){
if(h[i][j]==h[i+1][j]) res--;
}
}
cout << res << endl;
return 0;
}
法三:堆,最长公共下降子序列
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int n;
LL h[N];
struct Node{
int l,r;
LL v;
bool operator< (const Node& w) const{
if(v!=w.v) return v<w.v;
return l>w.l;
}
};
priority_queue<Node> q;
int main(){
cin >> n;
for(int i=0;i<n;i++) scanf("%lld",&h[i]);
for(int i=0;i<n;i++){
int j=i;
while(j<n && h[j]==h[j+1]) j++;
q.push({i,j,h[i]});
i=j;
}
int res=0;
while(q.top().v!=1){
Node t=q.top();
q.pop();
while(q.size() && q.top().v==t.v && q.top().l==t.r+1){
t.r=q.top().r;
q.pop();
}
q.push({t.l,t.r,(LL)sqrtl(t.v/2+1)});
res++;
}
cout << res << endl;
return 0;
}