【官方题解】二分加排序

【题目大意】

给你三个数字 $n,m,k$ ，再给你两组长度为n的数组 $a,b$ ，每过1天 $a_i=a_i+b_i$ ，题目要求求出最少多少天数组 $a$ 中有至少 $m$ 个数据不小于 $k$ ,输出这个天数，并且把不小于k分的总人数输出然后把这些人按照此时分数由高到低的排序方式输出他们编号，分数相同的人有限小编号。

【算法分析】

本题考查二分搜索、排序算法

我们不难发现有一个临界天数 $x$ 使得对于 $ \forall d \ge x$ 都有 $a_i + b_i \times d \ge k$ 的总人数不小于m，并且对于 $ \forall d < x$ 都有 $a_i+b_i \times d \ge k$ 的总人数小于 $m$ 。所以我们发现天数具有二段性，至此我们只需要二分来搜索最小可行天数即可。

然后我们记录并统计成绩超过k的同学再根据要求排序即可。

时间复杂度 O(nlogn) 。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll n,m,k,a[200005],b[200005];
bool fff(ll x){
	ll z=0;
	for (int i=1;i<=n;i++) if (a[i]+b[i]*x>=k) z++;
	return z>=m;
}
bool cmp(pair<ll,ll> x,pair<ll,ll> y){
	return x.first==y.first?x.second<y.second:x.first>y.first;
}
int main(){
	cin>>n>>m>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) cin>>b[i];
	ll l=0,r=1e9,mid;
	while(l!=r){
		mid=l+r>>1;
		if (fff(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	ll z=0;
	vector<pair<ll,ll>> e;
	for (int i=1;i<=n;i++){
		a[i]+=b[i]*l;
		if (a[i]>=k) z++,e.push_back({a[i],i});
	}
	cout<<z<<endl;
	sort(e.begin(),e.end(),cmp);
	for (auto u:e){
		cout<<u.second<<' ';
	}
}