2011-08-21 12:12:41Morris
b212. E. 不景氣的年代
b212. E. 不景氣的年代
內容 ：
框框國也糟逢金融巨浪侵襲，全國上下面臨嚴重的通貨緊縮問題。為了避免大蕭條再次來臨，框框國王這次不惜動搖國本也要拯救經濟，決定要給國內的每個人一萬元的大紅包來刺激消費，好度過這次景氣寒冬。
但是要如何把這一萬元交到人民的手上，可以使用的手段總共有
1. 發放現金
2. 退稅
3. 發放消費卷
儘管如次，框框國內卻有了許多不同的聲音。為了到底要哪一種手段，框框國內已經吵了一個月了，卻沒有任何結論。
最後，框框國民們願意接受一種妥協，但是每個人仍然堅持著每個管道至少要配發多少數額，才是公平之道。
民主的框框國王決定要採用最多人同意的辦法，可惜框框國王雖然長的帥，卻不知道如何解決這個問題。他決定請教一群專家團隊，來解決這個大難題。現在，你知道最好的辦法到底可以讓多少框框國民滿意呢？
輸入說明
：
第一行有一個數字 k , 1 <= k <= 20 代表共有 k 筆測資
每筆測資第一行有兩個整數 N
1 <= N <= 5000 , 代表框框國內總共有 N 位框框國民
接下來有 M 行，每行有三個大於等於零的整數 a, b, c
0 <= a + b + c <= 10000
分別代表該位框框國民期待在現金上面至少獲得 a 元
在退稅上面至少獲得 b 元
在消費卷上至少獲得 c 元
輸出說明
：
每筆測資輸出一行，每行有一個數字，代表最多可以讓多少框框國民滿意。
範例輸入 ：
3 3 10000 0 0 0 10000 0 0 0 10000 3 5000 0 0 0 2000 0 0 0 4000 5 0 1250 0 3000 0 3000 1000 1000 1000 2000 1000 2000 1000 3000 2000
範例輸出 ：
1 2 5
提示
：
出處
：
2008 NPSC 高中組決賽
作法 : Binary Indexed Tree+窮舉
窮舉 a 由小到大, 次來 b 由小到大,
在次窮舉的時候, 將符合小於等於 a 的組, 將 c 插入 BIT 中,
檢查有多少組 c <= 10000-a-b
BIT 的常數 比 線段樹小很多,
不過必須了解 能存的數字從 1 開始, 所以此題要平移 1, 再來要符合疊加原理
/**********************************************************************************/作法 : Binary Indexed Tree+窮舉
窮舉 a 由小到大, 次來 b 由小到大,
在次窮舉的時候, 將符合小於等於 a 的組, 將 c 插入 BIT 中,
檢查有多少組 c <= 10000-a-b
BIT 的常數 比 線段樹小很多,
不過必須了解 能存的數字從 1 開始, 所以此題要平移 1, 再來要符合疊加原理
/* Problem: b212 "E. 不景氣的年代" from 2008 NPSC 高中組決賽 */
/* Language: C */
/* Result: AC (688ms, 472KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-21 12:06:22 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
typedef struct {
int a, b, c;
}INF;
INF A[5000], B[5000], X[5000];
void Merge(int l, int m, int h,INF Data[]) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= h)
if(Data[In1].a < Data[In2].a
|| (Data[In1].a == Data[In2].a && Data[In1].b < Data[In2].b))
X[Top++] = Data[In1++];
else X[Top++] = Data[In2++];
while(In1 <= m) X[Top++] = Data[In1++];
while(In2 <= h) X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
void MergeSort(int l, int h, INF Data[]) {
if(l < h) {
int m=(l+h)/2;
MergeSort(l ,m, Data);
MergeSort(m+1,h, Data);
Merge(l, m, h, Data);
}
}
int C[10002] = {}, LOW[10002];
int Modify (int N, int L) {
while(N <= L) {
C[N] += 1;
N += LOW[N];
}
}
int Operator (int N) {
int Sum = 0;
while(N) {
Sum += C[N];
N -= LOW[N];
}
return Sum;
}
main() {
int k, n, a, b;
for(a = 0; a < 10002; a++) LOW[a] = a & (-a);
scanf("%d", &k);
while(k--) {
scanf("%d", &n);
for(a = 0; a < n; a++)
scanf("%d %d %d", &A[a].a, &A[a].b, &A[a].c),
B[a].a = A[a].b, B[a].b = A[a].a, B[a].c = A[a].c;
MergeSort(0, n-1, A), MergeSort(0, n-1, B);
int Pa, Pb, Pc, t, Ans = 0;
for(a = 0; a < n; ) {
Pa = A[a].a;
while(a < n && A[a].a <= Pa) a++;
memset(C, 0, (10000-Pa+2)*4);
for(b = 0; b < n && Pa+B[b].a <= 10000; ) {
Pb = B[b].a, Pc = 10000-Pa-Pb+1;
while(b < n && B[b].a <= Pb) {
if(B[b].b <= Pa) Modify(B[b].c+1, Pc);
b++;
}
t = Operator(Pc);
Ans = Ans > t ? Ans : t;
}
}
printf("%d\n", Ans);
}
return 0;
}
上一篇：d956. G. 失落的維京戰機
下一篇：b207. F. 世界盃