codechef - Discrepancies in the Voters List 題解

codechef的本題算法也不難，但是codechef喜歡大數據，動不動就過萬過十萬，輸入輸出處理不好就會超時。

就像本題最大數據可能達到15萬個整數。普通輸入輸出鐵定超時了。

這裡使用fread和fwrite這兩個函數，設置好buffer，速度還是相當快的，而且相對很多程序都比較簡單的了。

主要注意：

每個buffer數據塊和下一個buffer數據塊之間的銜接，不能破壞了最終需要的格式，也不要在輸入的時候破壞了數據連續性。

很低層的東西了，不過用多久慢慢熟悉了。

題意就是：找出三個數列中的所有在兩個數列都出現的數值。

原題：http://www.codechef.com/problems/VOTERS/

處理算法的代碼還不到輸入輸出代碼的一半呢。

#pragma once

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int DiscrepanciesintheVotersList()
{
	int N1, N2, N3, n = 0;
	scanf("%d %d %d\n", &N1, &N2, &N3);
	int *A = new int[N1];
	int *B = new int[N2];
	int *C = new int[N3];

	char buffer[10000];
	int num = 0, id = 0, i = 0, j = 0, k = 0;
	while ((n = fread(buffer, 1, 10000, stdin)) > 0)
	{		
		for (int i = 0; i < n; i++)
		{
			if ('0' <= buffer[i] && buffer[i] <= '9')//避免有空格
			{
				num = num * 10 + (buffer[i] - '0');
			}
			else if (buffer[i] == '\n')
			{
				if (j < N1) A[j] = num;
				else if (j < N1+N2) B[j-N1] = num;
				else C[j-N1-N2] = num;
				j++;
				num = 0;
			}			
		}
	}
	if (0 != num) C[N3-1] = num;//需要額外處理一個數據，不能在循環中處理

	int newN = max(N1, max(N2, N3));
	int *D = new int[newN];

	id = 0, i = 0, j = 0, k = 0;
	while (i < N1 || j < N2 || k < N3)
	{
		int t = (1<<29);
		if (i < N1) t = min(t, A[i]);
		if (j < N2) t = min(t, B[j]);
		if (k < N3) t = min(t, C[k]);
		int c = 0;
		if (i < N1 && t == A[i]) c++, i++;
		if (j < N2 && t == B[j]) c++, j++;
		if (k < N3 && t == C[k]) c++, k++;
		if (c > 1) D[id++] = t;
	}

	printf("%d\n", id);
	for (int i = 0; i < id; )
	{
		int j = 0;
		while (j < 9500 && i < id)//這裡j要小於最大buffer 10000
		{
			int sum = 0, tmp = D[i], st = j;
			while (tmp)
			{
				sum = tmp % 10;
				tmp /= 10;
				buffer[j++] = sum + '0';
			}
			reverse(buffer+st, buffer+j);
			buffer[j++] = '\n';
			i++;
		}
		fwrite(buffer, 1, j, stdout);
		//每次都需要多打個'\n'，因為數據可能大於當次的buffer
	}

	delete []A;
	delete []B;
	delete []C;
	delete []D;
	return 0;
}