這是實驗室集訓開始第一次比賽的D題。
題意描述：給你n張卡片，每張卡片正反面都有顏色（兩面的顏色可能相同，或不同），將這些卡片放在桌面上，每次操作你可以將一張卡片翻面。問的是能否通過最少的翻面次數使得正面有一種顏色的數量>=卡片數的一半，并輸出翻面次數。
解題的大致思路是，用A[]統計出所有可能出現的顏色以及該種顏色出現的總次數，用B[]統計正面的顏色以及該種顏色出現的次數。如果A[]中有某種顏色出現的次數>=(n+1)/2，說明通過若干次翻面操作我們是可以達到目的的，這時只需再參照B[]，即可算出翻面次數。
思路很清晰，可是有一些不得不注意的細節。
1.當卡片兩面的顏色相同時，只能統計一次。
2.數據量很大，查找時要用二分。
3.如果一種顏色在只在反面出現，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
小鼠標 閱讀(358)
評論(0) 編輯 收藏 引用 所屬分類:
排序