14207: 【原4207】大主教带队

题目

题目描述

author: RayCiel 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4207

Description

大主教管n名ACM班小朋友，第i名小朋友的编程技能是\(a_i\)。

老板想要为一个新的编程比赛组成k个团队。众所周知，更多的小朋友参与竞争，胜利可能性更大。因此大主教必须安排不超过k个(至少一个)的非空队伍，这样小朋友的总数才能最大化。但大主教也知道每个队伍都应该保持平衡。这意味着每个队伍的每对小朋友的编程技能应该相差不超过5。队伍是相互独立的(这意味着两个来自不同队伍的小朋友在编程技能上的差异并不重要)。

有可能有些小朋友根本没有被纳入任何团队。

大主教的任务是报告不超过k个(至少一个)非空平衡团队中可能的最大小朋友总数。

Input Format

输入的第一行包含两个整数n和k\((1 \leq k \leq n \leq 5000)\)对应的是小朋友人数和最大队伍数。

输入的第二行包含n个整数\(a_1,a_2，…，a_n(1 \leq a_i \leq 10^9)\)，其中\(a_i\)是第i个学生的编程技能。

Output Format

一个整数——不超过k(至少一个)的非空平衡队伍中小朋友总数的最大值

Sample Input

5 2
1 2 15 15 15

Sample Output

5

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int a[5009] = { 0 };

template <class T, class T_val = decltype(*declval<T>()),
    class Compare = bool (*)(T_val, T_val)>
    void quick_sort(T start, T end,
        Compare cmp = [](T_val a, T_val b) {return a < b; }) {
    if (start == end)
        return;
    auto i = start, j = end;
    --j;
    if (i == j)
        return;
    //交换
    auto key = *start;
    for (bool status = true; i != j;) {
        if (status) {
            if (cmp(*j, key)) {
                *i = *j;
                ++i;
                status = false;
            }
            else
                --j;
        }
        else {
            if (cmp(key, *i)) {
                *j = *i;
                --j;
                status = true;
            }
            else
                ++i;
        }
    }
    *i = key;
    //递归
    quick_sort(start, ++i, cmp);
    quick_sort(i, end, cmp);
}

int dp_data[5000][5000] = { 0 };
int n;

int dp(int pos, int k) {
    if (pos >= n || k <= 0) {
        return 0;
    }
    if (dp_data[pos][k] > 0)
        return dp_data[pos][k];
    int ans1 = dp(pos + 1, k), ans2 = 0, i = pos;
    for (; i < n; ++i) {
        if (a[i] - a[pos] <= 5)
            ++ans2;
        else
            break;
    }
    ans2 += dp(i, k - 1);
    dp_data[pos][k] = ans1 < ans2 ? ans2 : ans1;
    return dp_data[pos][k];
}

int main() {
    int k;
    cin >> n >> k;

    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    quick_sort(a, a + n);

    cout << dp(0, k);

    return 0;
}

skyzh's solution

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct Range {
    Range(int L, int R) : L(L), R(R) {}
    int L, R;
    friend bool operator< (const Range& a, const Range& b) {
        if ((a.R - a.L) == (b.R - b.L)) return a.L < b.L;
        return (a.R - a.L) < (b.R - b.L);
    }
};

int main() {
    priority_queue <Range, vector<Range>, less<Range> > t;
    int n, k;
    int cap[10000] = { 0 };
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> cap[i];
    sort(cap, cap + n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (cap[i] - cap[j] <= 5) {
                t.push(Range(j, i));
            }
        }
    }
    bool visited[10000] = { 0 };
    while (!t.empty() && k > 0) {
        Range r = t.top();
        bool found = true;
        for (int i = r.L; i <= r.R; i++) {
            if (visited[i]) {
                found = false;
                break;
            }
        }
        if (found) {
            for (int i = r.L; i <= r.R; i++) {
                visited[i] = true;
            }
            --k;
        }
        t.pop();
    }
    int sum = 0;
    for (int i = 0; i < n; i++) if (visited[i]) ++sum;
    cout << sum << endl;
    return 0;
}