codechef Carvans 題解

本題其實就是計算數組中後一個數比前一個數小的個數，加上第一個數。

聽起來好容易哦。

但是這裡的考的是大數據，超過4m的數據等著輸入。

怎麼搞，不對輸入輸出熟悉，是鐵定超時的。

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

這裡使用了兩種方法，也是目前我覺得最好的方法了：

1 使用gechar

2 使用fread

其中第一種比較好使用，但是第二種方法真叫我頭疼。最後終於搞定。

之前一直卡著，是因為程序結果沒處理好mix up了。一定要分開處理，一個處理輸入輸出的函數，一個處理邏輯的函數。

mix up了就好頭疼，因為有空格符，有換行符，有輸入結尾，光著三種情況就會亂如麻。

教訓啊，程序結構沒分好，越做越頭疼的。不要小瞧了任何“容易”的題目了。

還有這裡的數據居然超過了1 << 30這個值了，所以害我隨意地使用了1 <<30代替了整數最大值，一直答案錯誤。

1 下面使用getcha處理的程序

#include 

//教訓：不要隨便使用1<<30作為整數最大值

int Carvans()
{
	auto scanInt = []()
	{
		char c = getchar();
		while (c < '0' || '9' < c)
		{
			c = getchar();
		}
		int num = 0;
		while ('0' <= c && c <= '9')
		{
			num = (num<<3) + (num<<1) + c - '0';
			c = getchar();
		}
		return num;
	};

	int T = scanInt();
	while (T--)
	{
		int N = scanInt();
		int curMin = 2147483647, a = 0, ans = 0;//本題數據居然會大於1<<30
		for (int i = 0; i < N; i++)
		{
			a = scanInt();
			if (a <= curMin)
			{
				curMin = a;
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

2 下面是使用fread的，速度更加快，不過幾個細節沒處理好就會有bug，邏輯混了更加容易出bug了，自己想出來處理好，難度還是相當高的。

下面程序應該沒有bug了。

#include 

char BufferCarvans[4096];
int idCar = 0, Ccar = 0;

int getFromBufferCar()
{
	int num = 0;
	bool first = true;
	while (true)
	{
		if (idCar >= Ccar) 
		{
			idCar = 0;
			Ccar = fread(BufferCarvans, 1, 4096, stdin);
		}
		if (Ccar == 0) return num;//讀到無數據，返回最後一個值

		while (first && idCar < Ccar && (BufferCarvans[idCar] < '0' || 
			BufferCarvans[idCar] > '9')) idCar++;

		while (idCar < Ccar && BufferCarvans[idCar] >= '0' &&
			BufferCarvans[idCar] <= '9')
		{
			num = (num<<3) + (num<<1) + BufferCarvans[idCar] - '0';
			idCar++;
			first = false;
		}
		if (idCar < Ccar && (BufferCarvans[idCar] < '0' || 
			BufferCarvans[idCar] > '9'))
		{
			return num;
		}		
	}
	return 0;
}

int Carvans_3()
{
	int T, n = 0, a = 0, curMin = 0;
	scanf("%d\n", &T);

	while (T--)
	{
		n = getFromBufferCar();
		curMin = getFromBufferCar();
		int ans = 1;
		for (int i = 1; i < n; i++)
		{
			a = getFromBufferCar();
			if (a <= curMin)
			{
				curMin = a;
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}