白駿2110、ルータを取り付けます

8347 ワード
問題を解く アルゴリズム#アルゴリズム# 2022 白駿 テキストリンク

質問する


https://www.acmicpc.net/problem/2110

に答える


プログラマーが解いたこの人の探索問題(まだアップロードされていない、入国審査問題)が同じかどうか、n、lg 10000000で解決できる問題を探す.
ただ前回は下界を使わず上界にも正解があったので驚きましたが、ここでできなかったら前回の質問のテストケースはおかしいでしょう.
最初は間違っていた時は必ずh[0]を持っていなければならないから問題があったのかと思っていたが、よく考えてみると何もできないことはないようだ.もしだめなら、両側から回ってもいいと思います.(反例を考えたことがありますが、ないようです)

ミス

  • lb、UBコンテンツに時間があれば、整理して体得しましょう
  • の反例をよく考えてみましょう

    • コード#コード#

    #define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> home;

bool check(int c, int distance) {

	int prev_home = -100000000;
	int temp_c = c;

	for (int i = 0; i < home.size(); i++) {

		if (home[i] - prev_home >= distance) {

			prev_home = home[i];
			c--;

			if (c == 0)
				return true;

		}

	}

	return false;

}

int main() {

	int n, temp, r, l, m, c;

	scanf("%d %d", &n, &c);

	for (int i = 0; i < n; i++) {

		scanf("%d", &temp);
		home.push_back(temp);

	}

	sort(home.begin(), home.end());

	l = 0;
	r = 1000000000;

	while (l < r) {

		m = (r - l) / 2 + l;

		if (check(c, m)) {

			l = m + 1;

		}

		else {

			r = m;

		}

	}

	printf("%d", l - 1);

	return 0;

}
    JAvaベースのマルチステート
    HappyLeetcode39:Factorial Trailing Zeroes