14138: 【原4138】选组员

题目

题目描述

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

选组员

题目描述

为了提高同学们的学习效率，助教希望同学们分出小组。
现在在全班共\(n\)名同学中先选出第一个小组的成员，助教希望这个小组成为平均学习效率最高的模范小组，人数不限。
现在已知有一些同学聚在一起会对整组的学习效率带来一定的影响。平均学习效率定义为整组的学习效率除以人数。

输入格式

第一行两个整数\(n,m\)分别表示全班共\(n\)人，有\(m\)组同学聚在一起会对学习效率带来影响。
接下来\(2m\)行，每两行叙述一组同学的影响。
前一行两个整数\(k_i,c_i\)表示这\(k_i\)个同学聚在一起会使学习效率改变\(c_i\)。
后一行\(k_i\)个数表示这\(k_i\)个同学的编号(0 base)。

输出格式

一个数表示最大平均学习效率，保留到小数点后两位。

样例输入

4 4
2 2
0 1
2 3
1 2
2 4
0 2
3 -9
0 1 2

样例输出

2.00

数据规模

对于30%的数据有
\(n=4\)
对于30%的数据有
\(k_i\leq2\)
对于10%的数据满足上述两条件
对于100%的数据有
\(1\leq n\leq 15\)
\(0\leq m\leq 100\)
\(1\leq k_i\leq min(n,5)\)

ligongzzz's solution

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

int n, m;
bool visited[20] = { 0 };
int groups[109][20] = { 0 };
int val_data[109] = { 0 };
int val_num[109] = { 0 };

double ans = 0.0;

void cal_max(int pos) {
    if (pos == n) {
        double cur_ans = 0.0;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (visited[i]) {
                ++cnt;
            }
        }
        for (int i = 0; i < m; ++i) {
            bool flag = true;
            for (int j = 0; j < val_num[i]; ++j) {
                if (!visited[groups[i][j]]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cur_ans += double(val_data[i]);
            }
        }
        if (cnt > 0)
            cur_ans /= double(cnt);
        ans = cur_ans > ans ? cur_ans : ans;
        return;
    }
    visited[pos] = true;
    cal_max(pos + 1);
    visited[pos] = false;
    cal_max(pos + 1);
}

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &val_num[i], &val_data[i]);
        for (int j = 0; j < val_num[i]; ++j) {
            scanf("%d", &groups[i][j]);
        }
    }

    cal_max(0);
    printf("%.2f",ans);

    return 0;
}

WashSwang's solution

#include <iostream>
#include <iomanip>
using namespace std;
int sum,n,m,k[200],c[200],ex[20],num,x;
double ans;
int main() {
    cin>>n>>m;
    for (int i=0,j=1;i<15;i++,j<<=1) ex[i]=j;
    for (int i=0;i<m;++i){
        cin>>num>>c[i];
        for (int j=0;j<num;++j){
            cin>>x;
            k[i]+=ex[x];
        }
    }
    for (int i=0;i<(1<<n);++i){
        sum=0;
        num=0;
        for (int j=0;j<m;++j)
            if ((i&k[j])==k[j]) sum+=c[j];
        for (int j=i;j>0;j>>=1)
            if (j%2) num++;
        if (num!=0&&sum/double(num)>ans) ans=sum/double(num);
    }
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans;
    return 0;
}