Интервал расписания вопроса о выборе одинакового отрезка времени из каждого интервала - PullRequest
Новая
       32

Интервал расписания вопроса о выборе одинакового отрезка времени из каждого интервала

0 голосов
/ 21 марта 2019

Я боролся с вопросом об интервальном расписании, описание вопроса было следующим:

Описание: У Ланрана есть N друзей.Каждое воскресенье Ланран должен играть со своими друзьями.I-й друг может играть с Lanran время от времени b (a и b включены).Тем не менее, Ланран должен играть с каждым из своих друзей в течение одинакового количества времени.Ланран хочет играть со своими друзьями как можно дольше.Но он очень глупый.Поэтому он просит вас помочь рассчитать максимальное время, которое он может сыграть с каждым из своих друзей.

Входные данные В первой строке содержится одно целое число N. Каждая из следующих N (N <= 5000) строк содержит два целых числаa и b (1 <= a, b <= 10000), которые показывают интервал времени i-го друга. </p>

Выходные данные Выведите одно целое число, показывающее максимальное время, которое Ланран может играть с каждым из своихдрузья.

Я думаю, что это жадная проблема, и я выбираю минимальное время друга, а именно уже сыгранное время + возможное время игры до b друга, и играю с ним на i-й секунде.,Вот код: 

#include <bits/stdc++.h>

using namespace std;
const int N = 5010;
int n, s[N], e[N], cnt[N], me;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int low, int high) {
    int pivot = s[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (s[j] <= pivot) {
            i++;
            swap(&s[i], &s[j]);
            swap(&e[i], &e[j]);
        }
    }
    swap(&s[i + 1], &s[high]);
    swap(&e[i + 1], &e[high]);
    return (i + 1);
}

void quickSort(int low, int high) {
    if (low < high) {
        int pi = partition(low, high);
        quickSort(low, pi - 1);
        quickSort(pi + 1, high);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &s[i], &e[i]);
        if (e[i] < s[i]) { printf("0\n"); return 0; }
        if (e[i] > me) me = e[i];
    }
    quickSort(0, n - 1);
    for (int i = 1; i <= me; ++i) {
        int id = -1, mi = 0x7fffffff;
        for (int j = 0; j < n; ++j) {
            if (s[j] > i || i > e[j]) continue;
            if (cnt[j] + e[j] - i + 1 < mi) { id = j; mi = cnt[j] + e[j] - i + 1; }
        }
        ++cnt[id];
    }
    int ans = 0x7fffffff;
    for (int i = 0; i < n; ++i) if (cnt[i] < ans) ans = cnt[i];
    printf("%d\n", ans);
    return 0;
}

Так я что-то не так делаю?Я получил 7 неправильных ответов в 10 тестовых случаях.

1 Ответ

0 голосов
/ 21 марта 2019

Похоже, это то же самое, что и стандартная задача выбора активности. Я вставляю связанный стандартный алгоритм. Вы можете найти вики: https://en.wikipedia.org/wiki/Activity_selection_problem. Greedy-Iterative-Activity-Selector (A, s, f): 

Sort A by finish times stored in f

S = {A[1]} 
k = 1

n = A.length

for i = 2 to n:
   if s[i] ≥ f[k]: 
       S = S U {A[i]}
       k = i

return S
...