原题链接
考察:枚举
思路:
??枚举所有分配方案.这里采用的枚举方式是隔板法.也就是先枚举每个队的人数,然后将7个人全排列,按人数放隔板,计算答案.
Code
#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 10010,M = 10,S = 50;
int n,idx,nums[M],match[M],asc,bsc,csc,score[4];
PII p[S];
char a[N],b[N];
map<string,int> mp;
int get(int an,int bn)
{
for(int i=1;i<=an;i++) match[nums[i]] = 1;
for(int i=an+1;i<=an+bn;i++) match[nums[i]] = 2;
for(int i=an+bn+1;i<=7;i++) match[nums[i]] = 3;
int ans = 0;
for(int i=1;i<=n;i++)
{
int u = p[i].first,v = p[i].second;
if(match[u] == match[v] ) ans++;
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s likes %s",a,b);
if(!mp.count(a)) mp[a] = ++idx;
if(!mp.count(b)) mp[b] = ++idx;
p[i] = {mp[a],mp[b]};
}
scanf("%d%d%d",&asc,&bsc,&csc);
for(int i=1;i<=7;i++) nums[i] = i;
int ans1 = 0x3f3f3f3f,ans2 = 0;
do{
for(int i=1;i<7;i++)
for(int j=1;j<7-i;j++)
{//前1~i个人a 前i+1,i+j b i+j+1 7 c
int res = get(i,j);
score[1] = asc/i;
score[2] = bsc/j;
score[3] = csc/(7-i-j);
sort(score+1,score+4);
if(score[3]-score[1]<ans1)
{
ans1 = score[3]-score[1];
ans2 = res;
}else if(score[3]-score[1]==ans1) ans2 = max(res,ans2);
}
}while(next_permutation(nums+1,nums+8));
printf("%d %d\n",ans1,ans2);
return 0;
}