标签：qxiao qda int Median tot val1
- 难以直接求解。考虑用二分答案转化为判定（根据复杂度理论，判定的难度小于求解）。
- 当你想不到一个更新的视角看待问题时，不妨回顾一下你已有的想法，正解说不定就隐藏其中，只需要再深入一些
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[2005],b[2005][2005],v[2][2005][2005];
priority_queue<int>qxiao;
priority_queue<int,vector<int>,greater<int> >qda;
int len;
void clear()
{
len=0;
while(qxiao.size())
{
qxiao.pop();
}
while(qda.size())
{
qda.pop();
}
}
void update(int x)
{
if(len%2==0)
{
if(qda.empty()||x<=qda.top())
{
qxiao.push(x);
}
else
{
qxiao.push(qda.top());
qda.pop();
qda.push(x);
}
}
else
{
if(qxiao.empty()||x>=qxiao.top())
{
qda.push(x);
}
else
{
qda.push(qxiao.top());
qxiao.pop();
qxiao.push(x);
}
}
len++;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
clear();
for(int j=i;j<=n;j++)
{
update(a[j]);
b[i][j]=qxiao.top();
}
}
int l=1,r=1000000000;
while(l<r)
{
int mid=(l+r)>>1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
v[0][i][j]=v[0][i-1][j]+v[0][i][j-1]-v[0][i-1][j-1];
v[1][i][j]=v[1][i-1][j]+v[1][i][j-1]-v[1][i-1][j-1];
if(i>j)
{
continue;
}
v[0][i][j]+=(b[i][j]<=mid);
v[1][i][j]+=(b[i][j]>=mid);
}
}
int val0=0,val1=0;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
int v0=v[0][j][j]-v[0][i-1][j]-v[0][j][i-1]+v[0][i-1][i-1];
int v1=v[1][j][j]-v[1][i-1][j]-v[1][j][i-1]+v[1][i-1][i-1];
int m=j-i+1;
int tot=m*(m-1)/2+m;
val0+=(v0>=(tot+1)/2);
val1+=(v1>=tot-(tot+1)/2+1);
}
}
if(val0>=val1)
{
r=mid;
int tot=n*(n-1)/2+n;
if(val0>=(tot+1)/2&&val1>=tot-(tot+1)/2+1)
{
cout<<mid<<endl;
return 0;
}
r--;
}
else
{
l=mid;
int tot=n*(n-1)/2+n;
if(val0>=(tot+1)/2&&val1>=tot-(tot+1)/2+1)
{
cout<<mid<<endl;
return 0;
}
l++;
}
}
cout<<l<<endl;
return 0;
}
标签：qxiao,
qda,
int,
Median,
tot,
val1
From： https://www.cnblogs.com/watersail/p/18417930