数据结构算法——1017. 座位分配

本文主要是介绍数据结构算法——1017. 座位分配，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

标题

in1
3
7 3 7

out1
#1
1 4 7 10 13 16 19 22 25 28
31 34 37 40 43 46 49 52 55 58
61 64 67 70 73 76 79 82 85 88
91 93 95 97 99 101 103 105 107 109
111 113 115 117 119 121 123 125 127 129
131 133 135 137 139 141 143 145 147 149
151 153 155 157 159 161 163 165 167 169
#2
2 5 8 11 14 17 20 23 26 29
32 35 38 41 44 47 50 53 56 59
62 65 68 71 74 77 80 83 86 89
#3
3 6 9 12 15 18 21 24 27 30
33 36 39 42 45 48 51 54 57 60
63 66 69 72 75 78 81 84 87 90
92 94 96 98 100 102 104 106 108 110
112 114 116 118 120 122 124 126 128 130
132 134 136 138 140 142 144 146 148 150
152 154 156 158 160 162 164 166 168 170

in2
3
3 7 10

out2
#1
1 4 7 10 13 16 19 22 25 28
31 34 37 40 43 46 49 52 55 58
61 64 67 70 73 76 79 82 85 88
#2
2 5 8 11 14 17 20 23 26 29
32 35 38 41 44 47 50 53 56 59
62 65 68 71 74 77 80 83 86 89
91 93 95 97 99 101 103 105 107 109
111 113 115 117 119 121 123 125 127 129
131 133 135 137 139 141 143 145 147 149
151 153 155 157 159 161 163 165 167 169
#3
3 6 9 12 15 18 21 24 27 30
33 36 39 42 45 48 51 54 57 60
63 66 69 72 75 78 81 84 87 90
92 94 96 98 100 102 104 106 108 110
112 114 116 118 120 122 124 126 128 130
132 134 136 138 140 142 144 146 148 150
152 154 156 158 160 162 164 166 168 170
172 174 176 178 180 182 184 186 188 190
192 194 196 198 200 202 204 206 208 210
212 214 216 218 220 222 224 226 228 230

思路

用个链表队列
每个节点存放一个int数组记录位置，队满了就可以删除，而链表队列中本身还有个地址数组方便后续输出

代码

#include<iostream>
using namespace std;

struct dot
{
    int num;
    int size;
    int* location;

    dot* prev;
    dot* next;
};
struct line
{
    dot* head;
    dot** arr;
    int arr_n;
    line(int n)
    {
        head = new dot;
        head->prev = NULL;
        head->next = NULL;
        head->num = 0;
        head->size = 0;
        arr = new dot* [n];
        arr_n = 0;
    }

    void insert(int n)
    {
        if(head->next == NULL)
        {
            head->next = new dot;
            head->next->next = head->next->prev = head->next;
            head->next->num = n * 10;
            head->next->size = 0;
            head->next->location = new int[n * 10];
            arr[arr_n++] = head->next;
            return; 
        }

        dot* record = head->next->prev;
        record->next = new dot;
        head->next->prev = record->next;
        record->next->prev = record;
        record->next->next = head->next;
        record->next->num = n * 10;
        record->next->location = new int[n * 10];
        arr[arr_n++] = record->next;
    }
    void cal()
    {
        int loc = 0;
        bool flag = 1;
        while(head->next)
        {
            dot* h = head->next;
            if(h == h->next)
            {
                loc += 2;
                if(flag)
                {
                    flag = false;
                    loc--;
                }
                h->location[h->size++] = loc; 
                if(h->size == h->num)
                    break;
            }
            else
            {
                dot*h = head->next;
                h->location[h->size++] = ++loc;
                if(h->size == h->num)
                {
                    h->prev->next = h->next;
                    h->next->prev = h->prev;
                }
            }

            head->next = head->next->next;
        }
    }
    void out()
    {
        for(int i = 0; i < arr_n; i++)
        {
            cout << "#" << i + 1 <<endl;
            int a = 1;
            for(int j = 0; j < arr[i]->num; j++)
            {
                if(a % 10 == 0)
                    cout << arr[i]->location[j] << endl;
                else
                    cout << arr[i]->location[j] << " ";
                a++;
            }
        }
    }

};

int main()
{
    int n;
    cin >> n;
    line L(n);
    for(int i = 0; i < n; i++)
    {
        int b;
        cin >> b;
        L.insert(b);
    }
    L.cal();
    L.out();
}

这篇关于数据结构算法——1017. 座位分配的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！