这是实验室集训开始第一次比赛的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
小鼠标 阅读(337)
评论(0) 编辑 收藏 引用 所属分类:
排序