2014-03-28 08:22:31| 人氣4,426| 回應3 | 上一篇 | 下一篇

[UVA][塊狀鏈表] 12634 - Pairing Boys and Girls

Input

First line of the input file will contain a positive integer T (T ≤ 10). Hence follow T test cases.

In the first line of each test case there will be a positive integer N (N ≤ 100,000). Each of the next N lines describes an insertion operation for a group. Each line will contain 3 integers “type where count”.

· type is 0 if the group is of boys, type will be 1 if the group is of girl.

· where denotes the position where this group will be inserted. If where = 0, then this group will be inserted in front of the entire line, otherwise that group will be inserted after where number of people. It will not exceed total number people in the line.

· count denotes number of boys/girls in that group. 1 ≤ count ≤ 10,000

Output

For each case output the case number “Case x:”. Hence for each insertion operation, output the maximum possible pairing after the insertion operation is performed. There will be no blank line between output for different test cases. For details please go through the sample input output.

Sample Input Output for Sample Input

1 1 4

0 3 3

0 0 2

1 0 1

Case 1:

Case 2:

Problemsetter: Md. Mahbubul Hasan, Special Thanks: Tasnim Imran Sunny

題目描述：

在一條線性隊伍，每個男生可以向後找到一位女生匹配跳舞，每回合音樂結束，可以對於其中一個位置插入一團男生或者女生，請問每回合最高的匹配次數為何。

一開始隊伍有一個男生在最前面，編號從 1 開始計算。

題目解法：

假設不考慮效率問題，計算最大匹配次數是採用線性時間去計算，相當於 O(n) 的貪婪做法。

為了要維護隊列有序性，要不就先展開、離線處理，也有可能用 splay tree 完成 ?

假設效率要求也不高，那麼塊狀鏈表會是一個好的選擇。

對於一個塊狀，可以內部自行匹配，而多餘的女生，可以跟前方(編號較小)的塊中，與多餘的男生匹配。

這方面也符合貪婪作法，不影響正確性。

因此每個操作都是 O(sqrt(n))，還好 Accepted 了。

#include <stdio.h>
#include <stdlib.h>
struct Node {
   int v[512], v_size;
   int v_sum; // sigma(abs(v[i]))
   int v_pair; // this problem matched.
   int v_girl; // unmatch girl.
   Node *next;
   Node() {
       v_size = v_sum = v_pair = v_girl = 0;
       next = NULL;
   }
};
int P_SIZE = 250;
void freeList(Node *head) {
    Node *idx = head, *pre = NULL;
    while(idx != NULL) {
        pre = idx, idx = idx->next;
        delete pre;
    }
}
int calcList(Node *head) {
   int mpair = 0;
   int boy = 0;
   Node *idx = head, *pre = NULL;
    while(idx != NULL) {
       mpair += idx->v_pair;
       mpair += boy < idx->v_girl ? boy : idx->v_girl;
       boy -= idx->v_girl;
       if(boy < 0)   boy = 0;
       boy += idx->v_sum - idx->v_pair*2 - idx->v_girl;
       pre = idx, idx = idx->next;
    }
   return mpair;
}
void reCalculate(Node *p) {
   int sum = 0, mpair = 0, boy = 0, girl = 0;
   for(int i = 0; i < p->v_size; i++) {
       if(p->v[i] > 0)   {
           boy += p->v[i];
       } else {
           mpair += boy < -(p->v[i]) ? boy : -(p->v[i]);
           girl += boy + p->v[i] < 0 ? -(boy + p->v[i]) : 0;
           boy = boy + p->v[i] > 0 ? boy + p->v[i] : 0;
       }
       sum += abs(p->v[i]);
   }
   p->v_sum = sum, p->v_pair = mpair, p->v_girl = girl;
}
Node* insertNode(Node *head, int where, int val) {
   if(where == 0) {
       Node *p = new Node();
       p->v[0] = val, p->v_size = 1;
       p->next = head;
       reCalculate(p);
       return p;
   }
   int sum = 0;
    Node *idx = head, *pre = NULL;
    while(idx != NULL) {
       sum += idx->v_sum;
       pre = idx, idx = idx->next;
       if(sum >= where)
           break;
    }
    if(sum == where) {
       Node *p = new Node();
       p->next = pre->next, pre->next = p;
       p->v[0] = val, p->v_size = 1;
       reCalculate(p);
       return head;
    }
    sum -= pre->v_sum;
    for(int i = 0; i < pre->v_size; i++) {
       if(sum + abs(pre->v[i]) >= where) {
           Node *p = new Node();
           int div = i+1;
           int diff = sum + abs(pre->v[i]) - where;
           p->next = pre->next, pre->next = p;
           p->v[p->v_size++] = val;
           if(diff > 0) {
               if(pre->v[i] > 0) {
                   p->v[p->v_size++] = diff;
                   pre->v[i] -= diff;
               } else {
                   p->v[p->v_size++] = -diff;
                   pre->v[i] += diff;
               }
           }
           for(int j = div; j < pre->v_size; j++)
               p->v[p->v_size++] = pre->v[j];
           pre->v_size = div;
           reCalculate(p);
           reCalculate(pre);
           break;
       }
       sum += abs(pre->v[i]);
    }
    return head;
}
void maintainList(Node *head) {
    Node *idx = head, *p;
    while(idx != NULL && idx->next != NULL) {
        if(idx->v_size + idx->next->v_size <= 2 * P_SIZE) { // merge
            p = idx->next;
            for(int i = idx->v_size, j = 0; j < p->v_size; i++, j++)
                idx->v[i] = p->v[j];
            idx->v_size += p->v_size;
            idx->next = p->next;
            delete p;
           reCalculate(idx);
        }
        idx = idx->next;
    }
}
void printList(Node *head) {
    Node *idx = head;
    int i, j = 0;
    while(idx != NULL) {
        printf("%d [%d, %d]: ", ++j, idx->v_pair, idx->v_girl);
        for(i = 0; i < idx->v_size; i++)
            printf("%d ", idx->v[i]);
        puts("");
        idx = idx->next;
    }
    puts("====");
}
int main() {
   int testcase, cases = 0, N;
   scanf("%d", &testcase);
   while(testcase--) {
       printf("Case %d:\n", ++cases);
       scanf("%d", &N);
       Node *head = NULL;
       head = new Node();
       head->v[0] = 1, head->v_size = 1;
       head->v_sum = 1, head->v_pair = 0;
       for(int i = 0; i < N; i++) {
           int girl, where, cnt;
           scanf("%d %d %d", &girl, &where, &cnt);
           if(girl)   cnt = -cnt;
           head = insertNode(head, where, cnt);
           maintainList(head);
           //printList(head);
           printf("%d\n", calcList(head));
       }
       freeList(head);
   }
   return 0;
}
/*
2
3
1 1 4
0 3 3
0 0 2
1
1 0 1
*/

我要檢舉

#12634#Pairing Boys and Girls#塊狀鏈表

台長： Morris

您可能對以下文章有興趣

[UVA] 10701 - Pre, in and post

[UVA][Floyd] 821 - Page Hopping

[UVA][dp] 672 - Gangsters

[UVA] 400 - Unix ls

人氣(4,426) | 回應(3)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][隨機、亂做] 10715 - Cat
此分類上一篇:[UVA][模擬退火] 10228 - Star not a Tree

回應(3)