比赛 |
20111012 |
评测结果 |
AAAAAAAWAA |
题目名称 |
配药惊魂 |
最终得分 |
90 |
用户昵称 |
fanzeyi |
运行时间 |
0.000 s |
代码语言 |
C |
内存使用 |
0.00 MiB |
提交时间 |
2011-10-12 21:44:20 |
显示代码纯文本
/*
ID: fanzeyi1
LANG: C
TASK: drug
*/
/*
* =====================================================================================
*
* Filename: drug.c
* Version: 1.0
* Created: 10/12/2011 08:33:29 PM
* Revision: none
* Compiler: gcc
* Author: Zeray Fan, fanzeyi1994[at]gmail.com
* Company: http://www.fanhe.org/
*
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct {
double value;
int n;
}val;
int v, n, m;
int drug[17];
int cant[17][17];
int nv;
val value[65537];
short now[17];
short used[17];
int check(int i) {
int j;
for( j = 0 ; j < n ; j++ ) {
if(used[j]) {
if(cant[i][j]) {
return 0;
}
}
}
return 1;
}
void RemValue() {
int i;
int a = 0;
int b = 0;
for( i = 0 ; i < n ; i++ ) {
if(used[i]) {
a = a + 1;
b = b + drug[i];
}
}
if(!a) {
return;
}
value[nv].value = (double)b / a * sqrt(a);
value[nv++].n = a;
}
void getvalue(int times) {
if(times == n) {
RemValue();
return;
}
// 用药
if(check(times)) {
used[times] = 1;
getvalue(times + 1);
used[times] = 0;
}
getvalue(times + 1);
}
int cmp(const void *a, const void *b) {
val *c = (val *) a;
val *d = (val *) b;
if(c->value > d->value) {
return -1;
}else{
return 1;
}
}
int main(void) {
FILE *fin = fopen("drug.in","r");
FILE *fout = fopen("drug.out", "w");
int a, b;
int i, j;
int pack = 0;
double result = 0;
fscanf(fin, "%d %d %d", &v, &n, &m);
for( i = 0 ; i < n ; i++ ) {
fscanf(fin, "%d", &drug[i]);
}
for( i = 0 ; i < m ; i++ ) {
fscanf(fin, "%d %d", &a, &b);
cant[a-1][b-1] = 1;
cant[b-1][a-1] = 1;
}
getvalue(0);
qsort(value, nv, sizeof(val), cmp);
for( i = 0 ; i < nv ; i++ ) {
for( j = 0 ; j < value[i].n ; j++ ) {
pack = pack + 1;
result = result + value[i].value;
if(pack == v) {
fprintf(fout, "%.1lf\n", result);
return 0;
}
}
}
fprintf(fout, "%.1lf\n", result);
return 0;
}