Задача на бин поиск

Информатика
1

image
image747×716 28.9 KB

Можете объяснить как проверить подойдет ли какое то число советов для формирования при данных n команд

1 лайк
2

В m группах должно быть m*k студентов. Проверь, возможно ли взять m*k студентов, учитывая, что с одной группы нельзя взять больше, чем m студентов

2 лайка
3 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back    
#define fi first
#define se second
#define mp make_pair
#define speed ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const ll inf = 0;
const ll mod = 1e9+123;
int n, k;
ll a[55];
bool ok(ll m){
	ll s = 0;
	FOR(i, 0, n){
		if(a[i]<=m)s+=a[i];
		else s+=m;
	}
	return s>=k*m*1LL;
}
int main() {
    speed;
    cin>>k>>n;
    FOR(i, 0, n)cin>>a[i];
    ll l = 1, r = 1e18+100000;
    while(l+1<r){
    	ll m = l+(r-l)/2;
    	if(ok(m))l = m;
    	else r = m;
    }
    cout<<l;
    
    return 0;
}

Можете подсказать почему не проходит все тесты?

1 лайк
4 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back    
#define fi first
#define se second
#define mp make_pair
#define speed ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const ll inf = 0;
const ll mod = 1e9+123;
ll n, k;
ll a[55];
bool ok(ll m){
	ll s = 0;
	FOR(i, 0, n){
		s += min(a[i], m);
	}
	return s >= k*m;
}
int main() {
    speed;
    cin>>k>>n;
    FOR(i, 0, n)cin>>a[i];
    ll l = 0, r = 50*1e9+100;
    while(l+1<r){
    	ll m = l+(r-l)/2;
    	if(ok(m))l = m;
    	else r = m;
    }
    cout<<l;
    
    return 0;
}

Я поставил правильную границу для r.

3 лайка