数据好像弱了?错误代码也能ac
查看原帖
数据好像弱了?错误代码也能ac
201499
OneMore14楼主2021/2/27 21:33

一组数据 11 3 0 4 8 10 不能移走石头,最小应该是1吧,但我自己的ac代码输出是2

#include<iostream>
#include<cstring>
#include<cstdlib>
#include <map>
#include <climits>
#include<algorithm>
#include <stack>
#include <deque>
#define ll long long
using namespace std;

#define MAX_N 1000005

int dis[MAX_N];
int l, m, n;

bool check(int len) {
    int cnt = 0;
    int pre = 0;
    for (int i = 1; i <= n; i++) {
        if ((dis[i] - dis[pre]) >= len) {
            pre = i;
            cnt++;
        }
    }
    return cnt >= n - m;
}
int main(){

    cin >> l >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> dis[i];

    }
    dis[0] = 0;
    dis[n + 1] = l;

    int left = 0;
    int right = l;
    int ans = l;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

因为没有在check()的时候检查最后跳到n+1的那次长度

2021/2/27 21:33
加载中...