hdu 4671 Backup Plan

本文从WordPress迁移而来, 查看全部WordPress迁移文章

构造

题意有点难懂,读懂题就是比较简单的题了

n个服务器,m个数据库,每个数据库可以请求不同的服务器

对于一个数据库,有n个数字,为n个排列,表示它请求服务器的优先级

好像 2 1 3 4 表示这个数据库先请求2服务器,如果2服务器坏了就用1,接着3,4

题目要求在没有服务器坏掉以及只有一个服务器坏掉的时候,任意两个服务器的负载差不会大于等于2

1
2
3
4
看看sample
2 4 3 1 5
1 5 4 2 3
3 5 2 4 1

一开始用了213,213这些服务器的负载都是1,45的负载就是0,差值没有大于等于2

如果是45坏了,没有任何影响,还是用213

如果1坏了,第二台数据库就请求5服务器了,那么被使用的服务器是235,任意两个服务器的负载没超过2

同理3坏了,第三台服务器就请求5服务器,也是合法的

题目是要构造一个矩阵,任何可能的答案都行

比赛的时候是分类讨论的,要用文字说清楚比较麻烦,反而看代码容易懂

分的情况主要是

m<n

m=n

m能被n整除且大于n

m>n不能被整除

代码比赛的时候写的,比较简单的题目就不想修改了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 110
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,m;
int a[N][N];
int used[N];

void solve(){
int k = 0;
for(int i = 1; i <= m; i++){
if(k+1 <= n) a[i][1] = ++k;
else{
k = 1; a[i][1] = k;
}
}

for(int b = 1; b <= n; b++){
int pos = b , x1,x2,f;
if(b <= k){
f = 1; x1 = k+1; x2 = 1;
while(pos <= m){
if(f == 1) {
a[pos][2] = x1++;
if(x1 > n){ x1 = k+1; f = 2;}
}
else if(f == 2){
if(x2 != b){ a[pos][2] = x2++; }
else{ x2++; pos -= n; }
if(x2 > k){ x2 = 1; f = 1; }
}
pos += n;
}
}
else{
f = 1; x1 = k+1; x2 = 1;
while(pos <= m){
if(f == 1){
if(x1 != b) a[pos][2] = x1++;
else{ x1++; pos -= n; }
if(x1 > n) {x1 = k+1; f = 2;}
}
else{
a[pos][2] = x2++;
if(x2 > k) {x2 = 1; f = 1;}
}
pos += n;
}
}
}

for(int i = 1 ;i <= m; i++){
int x1 = a[i][1] , x2 = a[i][2];
int z = 1;
for(int j = 3; j <= n;){
if(z == x1 || z == x2) z++;
else{ a[i][j] = z++; j++; }
}
}
}

int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
if(m < n){
for(int i = 1; i <= m; i++){
a[i][1] = i; a[i][2] = m+1;
int k = 1;
for(int j = 3; j <= n;k++){
if(k != m+1 && k != i)
a[i][j++] = k;
}
}
}

else if(m == n){
for(int i = 1; i <= m; i++){
int k = (i % n);
if(k == 0) k = n;
for(int j = 1; j <= n; j++,k++){
if(k <= n) a[i][j] = k;
else a[i][j] = k - n;
}
}
}
else if(m % n == 0){
int k = 1;
for(int i = 1; i <= m; i++){
a[i][1] = k++;
if(k > n) k = 1;
}
for(int b = 1; b <= n; b++){
int pos = b;
int k = 1;
while(pos <= m){
if(k == b){
k++; pos -= n;
}
else{
a[pos][2] = k++;
}
if(k > n) k = 1;
pos += n;
}
}

for(int i = 1 ;i <= m; i++){
int x1 = a[i][1] , x2 = a[i][2];
int z = 1;
for(int j = 3; j <= n;){
if(z == x1 || z == x2) z++;
else{ a[i][j] = z++; j++; }
}
}
}

else solve();

for(int i = 1; i <= m; i++){
for(int j = 1; j < n; j++)
printf("%d ",a[i][j]);
printf("%d\n",a[i][n]);
}
}
return 0;
}