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;
}