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;
}