Morris' Blog

2014-03-28 08:22:31Morris

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

留言 3 收藏 0 推薦 0

Pairing Boys and Girls

Input: Standard Input

Output: Standard Output

In a dance party, Boys and Girls make a line before a song starts. Then a boy will pair up with a girl who is somewhere later in the line. The pairing will occur in such a way that number of pairs get maximized.

For example: If the Boy-Girl sequence in a line looks like: GGBGGBGB then there can be 2 pairs maximum. If we consider the line to be 1 indexed, the boy standing at 3^rd position pairs up with the girl at 4^th or 5^th position and the boy at 6^th position will pair up with the girl at 7^th position. They boy at 8^th position can not propose any girl, since there is no girl after him. Again, the boy at 3^rd position could not pair up with the girl at 7^th position, because if he would have paired up with her the number of pairing would be only 1, which is not maximum possible pairing.

After each song, boys and girls would line up in the same way before a new song. In this time, bunch of boys or girls may come. Manager will insert them at a certain position in the line. Then again pairing will occur. After each insertion you have to print number of maximum possible pairings. Initially there would be a boy in the line.

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
*/

上一篇：[UVA][模擬退火] 10228 - Star not a Tree

下一篇：[UVA][隨機、亂做] 10715 - Cat