codeforces（D. Max Median）二分答案

原题链接

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include 
#define pb push_back
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;int n,k,ans;
int a[200005],c[200005];
int pre[200005],num;
bool query(int key)
{for(int i=1;i<=n;i++){if(a[i]>=key){c[i]=1;}else{c[i]=-1;}}for(int i=1;i<=n;i++){pre[i]=pre[i-1]+c[i];}int val=0;for(int i=k;i<=n;i++){if((pre[i]-val)>0){return 1;}val=min(val,pre[i+1-k]);}return 0;
}
int main()
{scanf("%d %d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int l=1,r=n;while(l<=r){if(l==r){if(query(l)){ans=l;}break;}if(l+1==r){if(query(r)){ans=r;break;}if(query(l)){ans=l;break;}break;}int mid=(l+r)/2;if(query(mid)){l=mid;}else{r=mid-1;}}printf("%d\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！