Skip to content

14299: 【原4299】拼接碎发

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4299

问题描述

助教出题太辛苦了,以至于头发都碎成了一瓣儿一瓣儿的了,长度分别为$a_1,a_2,\dots,a_n$(均为整数),但助教本来有着等长的脱干$k$根秀发,,每根都长为$s$。她现在头秃到不知道自己原本到底有多少根头发以及头发有多长,她现在想让你们帮她把头发拼接起来恢复到碎前的状态(她不想浪费任何一根碎发,所以要所有的碎发都要用完),她希望得到最多的头发根数,即便每根都很短,但也可以长嘛不是。(即$k$最大,$s$最小。)

输入格式

输入共两行

第1行,一个整数$n$,表示有$n$根碎发。

第2行,$n$个用空格隔开的整数,表示每根碎发的长度。

输出格式

一行,用空格隔开的两个数字,分别是最多的头发根数$k$,和最小的头发长度$s$。

样例输入1

9
5 2 1 5 2 1 5 2 1

样例输出1

4 6

样例解释

九根碎发一共可以拼出4根长度均为6的头发。

数据范围与约束

对于30%的数据,$1\leq n\leq5$,$1\le a_i \le100$

对于60%的数据,$1\leq n\leq15$,$1\le a_i\le 1000$

对于100%的数据$1 \leq n \leq 27$,$1 \leq a_i \leq 1000$

HINT

(仅限B班,A班同学禁止使用sort)

如果你想要排序, 可以通过如下方法实现:

  • 包括头文件algorithm
  • 在命名空间内有sort(begin, end)函数, 其中beginend分别为排序开始的位置和结束的位置(左闭右开). 特别地, 如果想要让arr数组中下标为i至下标j之间(左闭右开)的元素从小到大排列的话, 可以调用sort(arr + i, arr + j)

例如:

#include <algorithm>
using namespace std;
int a[] = {3, 4, 1, 2};
int main() {
    sort(a + 1, a + 3);
    // 此时 a = {3, 1, 4, 2}
    sort(a, a + 4);
    // 此时 a = {1, 2, 3, 4}
    return 0;
}

需要注意的是,禁止使用algorithm库内的其他函数.

yyong119's solution

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MAX_N 30
#define MAX_A 1000
using namespace std;
int n, sum, max_len, len;
int a[MAX_N];
bool vis[MAX_N], flag;
void find(int len) {
    int pos = upper_bound(a, a + n, len) - a;
    for (register int i = pos - 1; i >= 0; --i)
        if (!vis[i] && len - a[i] >= 0) {
            vis[i] = true;
            if (len - a[i] == 0) {
                flag = true; return;
            }
            find(len - a[i]);
            if (flag) return;
            vis[i] = false;
        }
}

int main() {
    scanf("%d", &n);
    for (register int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
        max_len = max(max_len, a[i]);
    }
    sort(a, a + n);
    for (register int k = sum / max_len; k > 1; --k) {
        if (sum % k) continue;
        len = sum / k;
        // check for k and len
        memset(vis, false, sizeof(vis));
        for (register int i = 0; i < k; ++i) {
            flag = false;
            find(len);
            if (!flag) break;
        }
        if (flag) {
            printf("%d %d", k, len);
            return 0;
        }

    }
    printf("%d %d", 1, sum);
    return 0;
}