這是實(shí)驗(yàn)室集訓(xùn)開始第一次比賽的D題。
題意描述：給你n張卡片，每張卡片正反面都有顏色（兩面的顏色可能相同，或不同），將這些卡片放在桌面上，每次操作你可以將一張卡片翻面。問的是能否通過最少的翻面次數(shù)使得正面有一種顏色的數(shù)量>=卡片數(shù)的一半，并輸出翻面次數(shù)。
解題的大致思路是，用A[]統(tǒng)計(jì)出所有可能出現(xiàn)的顏色以及該種顏色出現(xiàn)的總次數(shù)，用B[]統(tǒng)計(jì)正面的顏色以及該種顏色出現(xiàn)的次數(shù)。如果A[]中有某種顏色出現(xiàn)的次數(shù)>=(n+1)/2，說明通過若干次翻面操作我們是可以達(dá)到目的的，這時只需再參照B[]，即可算出翻面次數(shù)。
思路很清晰，可是有一些不得不注意的細(xì)節(jié)。
1.當(dāng)卡片兩面的顏色相同時，只能統(tǒng)計(jì)一次。
2.數(shù)據(jù)量很大，查找時要用二分。
3.如果一種顏色在只在反面出現(xiàn)，B[]中是找不到它的。以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#define LEN 2000200
#define LENC 200010
#define MAX 10000000
typedef struct
{
int c;//color
int n;//time
}Node;
typedef struct
{
int c;
int f;//front or down, 1 or 0
}Color;
Color C[LENC];
int lenc;
Node A[LEN];
int lena;
Node B[LEN];
int lenb;
int cmpc(const void *a, const void *b)
{
Color *a0 = (Color*)a;
Color *b0 = (Color*)b;
return a0 -> c - b0 -> c;
}
int Min(int a, int b)
{
if(a < b)
return a;
return b;
}
int main()
{
int i, j;
int n;
while(scanf("%d", &n) != EOF)
{
int c1, c2;
lenc = 0;
for(i = 0; i < n; i++)
{
scanf("%d%d", &c1, &c2);
C[lenc].c = c1;
C[lenc++].f = 1;
if(c2 != c1)
{
C[lenc].c = c2;
C[lenc++].f = 0;
}
}
qsort(C, lenc, sizeof(Color), cmpc);
lenb = 0;//init B[]
for(i = 0; i < lenc; i++)
if(C[i].f == 1)
{
B[0].c = C[i].c;
B[0].n = 1;
lenb = 1;
i++;
break;
}
for(; i < lenc; i++)
{
if(C[i].f == 1)
{
if(C[i].c == B[lenb - 1].c)
{
B[lenb - 1].n++;
}
else
{
B[lenb].c = C[i].c;
B[lenb++].n = 1;
}
}
}
lena = 0;//init A[]
A[0].c = C[0].c;
A[0].n = 1;
lena = 1;
for(i = 1; i < lenc; i++)
{
if(C[i].c == A[lena - 1].c)
{
A[lena - 1].n++;
}
else
{
A[lena].c = C[i].c;
A[lena++].n = 1;
}
}
int psb = 0;
int mint = MAX;
for(i = 0; i < lena; i++)
{
int t = (n + 1) / 2;
if(A[i].n >= t)
{
int ii = 0;
int jj = lenb - 1;
int find = 0;
int mid;
while(ii <= jj)//binSearch
{
mid = (ii + jj) / 2;
if(B[mid].c == A[i].c)
{
find = 1;
break;
}
else if(A[i].c < B[mid].c)
{
jj = mid - 1;
}
else
ii = mid + 1;
}
if(find == 1)
{
int k = t - B[mid].n;
mint = Min(mint, k);
}
else
mint = Min(mint, t);
psb = 1;
}
}
if(psb == 1)
{
if(mint >= 0)
printf("%d\n", mint);
else
printf("0\n");
}
else
printf("-1\n");
}
//system("pause");
}
posted on 2012-08-06 15:16
小鼠標(biāo) 閱讀(379)
評論(0) 編輯 收藏 引用 所屬分類:
排序