二分题目求教
  • 板块学术版
  • 楼主weiyuqing9
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/12/10 21:02
  • 上次更新2023/10/26 23:52:21
查看原帖
二分题目求教
749622
weiyuqing9楼主2022/12/10 21:02

有n个人排成一排,第i个人的体力为ai,你只能挑选出一段连续的人让他们出列去跑操。因为你不敢选一些体力太差的人去跑,担心他们太累,所以你选的人的体力值不能小于X。可是你希望每次能多选一些人去跑操,你需要求出至少能够选y个人去跑操时x的最大值。 如果始终都不能选出y个人,输出-1。

输入的第一行是两个 正整数n和y

输入的第二行是n个正整数ai。

就问4和5

(4)A.l<=r B.l+1<=r (选A)

(5)A.(r+l)/2 B.(r-l+1)/2 C.l+(r-1)/2 D.(r+l+1)/2 (选C)

Why?

#include<bits/stdc++.h>
using namespace std;
int n,y,a[100005];
int chk(int x)
{
    int ans=0;
    int tot=0;
    for (int i=1; i<=n; i++)
	{
        if (a[i]>=x) tot++;
        else
			{
            tot=0;
        }
        ans=max(ans,tot);
    }
    return ans>=y;
}
int main()
{	
	cin>>n>y;
	for (int i=1; i<=n; i++) cin>>a[i];
	int ans=-1;
	int l=1, r=200000000;
	while (___(4)___)
	{
	    int mid=___(5)___;
	    if (chk(mid))
	    {
	    	ans=mid;
	    	l=mid+1;
		}else
	    	r=mid-1;
	}
	cout<<ans<<endl;
}
```c
2022/12/10 21:02
加载中...