항 전 OJ 문제 1557 권리 지수 문제 풀이 보고서

3420 단어 항주 전기 ACM
권리 지수
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 492    Accepted Submission(s): 337
Problem Description
선거 문제 에 서 는 모두 n 개의 작은 단체 가 있 고 작은 단체 마다 일 정량의 표를 가지 고 있다.이 중 m 개 소 단체의 표 수 와 전체 표 의 절반 을 넘 으 면 이 조합 은 '승리 연맹' 이다.n 개 단 체 는 몇 개의 승리 연맹 을 형성 할 수 있다.작은 단체 가 '관건 적 인 가입자' 가 되 려 는 조건 은 자신 이 있 는 승리 연맹 에서 이 작은 단체의 가입 이 부족 하면 이 연맹 은 승리 연맹 이 될 수 없다 는 것 이다.한 작은 단체의 권리 지 수 는 한 작은 단체 가 모든 승리 연맹 에서 '관건 적 인 가입자' 가 되 는 횟수 를 말한다.각 소 단체의 권리 지 수 를 계산 해 보 세 요.
 
Input
데 이 터 를 입력 하 는 첫 번 째 행 위 는 T 조 테스트 데이터 가 있 음 을 나타 내 는 정수 T 입 니 다.각 그룹 테스트 데이터 의 첫 번 째 행동 은 정수 n (0) 입 니 다.
 
Output
각 그룹의 테스트 데 이 터 를 같은 줄 에서 n 번 작은 단체의 권리 지 수 를 순서대로 출력 합 니 다.
 
Sample Input
 
   
2 1 10 7 5 7 4 8 6 7 5
 

Sample Output
 
   
1 16 22 16 24 20 22 16
 
————————————————————————————————————————————————————
先从小到大排序,然后DFS,应为如果没有排序,结果会丢失,原因是当在没有排序的情况下,当条件满足的时候就停止DFS,如果后面有数字满足条件,但可有可无的时候也算一种情况,没有考虑就错了

/****************************
 *Name:    .c
 *Tags:ACM water
 *Note:       ,  DFS,        ,     ,             ,           DFS,           ,              ,       
 ****************************/

#include 

void dfs(int, int);
void count();
int man[20][3];
int group[20];
int sum = 0;
int n, g;
int main()
{
      int t, i, s, j;
      scanf("%d", &t);
      while(t--) {
	    scanf("%d", &n);
	    sum = 0;
	    for(i = 0; i < n; i++) {
		  scanf("%d", &man[i][0]);
		  man[i][1] = 0;
		  man[i][2] = i;
		  sum += man[i][0];
	    }
	    if(n == 1) {
		  printf("%d
", 1); continue; } for(i = 0; i < n-1; i++) { for(j = 0; j < n-1-i; j++) { if(man[j][0] > man[j+1][0]) { s = man[j][0]; man[j][0] = man[j+1][0]; man[j+1][0] = s; s = man[j][2]; man[j][2] = man[j+1][2]; man[j+1][2] = s; } } } sum /= 2; for(i = 0; i < n; i++) { g = 0; s = man[i][0]; group[g++] = i; if(s > sum) { man[i][1] += 1; } else { dfs(i+1, s); } } for(i = 0; i < n-1; i++) { for(j = 0; j < n-1-i; j++) { if(man[j][2] > man[j+1][2]) { s = man[j][2]; man[j][2] = man[j+1][2]; man[j+1][2] = s; s = man[j][1]; man[j][1] = man[j+1][1]; man[j+1][1] = s; } } } printf("%d", man[0][1]); for(i = 1; i < n; i++) { printf(" %d", man[i][1]); } printf("
"); } return 0; } void dfs(int i, int s) { int j; for(i = i; i < n; i++) { s += man[i][0]; group[g++] = i; if(s > sum) { for(j = 0; j < g; j++) { if((s - man[group[j]][0]) <= sum) { man[group[j]][1]++; } } } else { dfs(i+1, s); } s -= man[i][0]; g--; } }

좋은 웹페이지 즐겨찾기