항 전 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--;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
항주 전기 1312 빨간색 과 검은색텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
