关于cin读入和scanf读入的快慢问题

scanf比cin快

关于scanf比cin快这个结论大家肯定都知道，但是一般情况下很难体现出来，只有当读入数据很大时，才会体现出scanf的快，以前从来都没有碰到过一道题是卡了cin输入的，但是今天终于碰到了！！！所以记录一下。

cin坑题

原题链接：Simone and graph coloring

题目出处：2020ICPC昆明站

本质上就是求最大下降子序列，并且求出以每一位作为结尾的最大下降子序列的长度，这个就是染色的数字。这里的最大下降子序列问题显然要用nlogn的做法，n2的做法肯定会T，于是就有了代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;

int n,a[N],col[N],arr[N];
int cnt,maxx = 1;
int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		cnt = 0;
		for(int i = 0;i < n;i++)
			cin >> a[i];
		col[0] = 1;
		arr[cnt++] = a[0];
		for(int i = 1;i < n;i++)
		{
			if(a[i] < arr[cnt-1])
			{
				arr[cnt++] = a[i];
				col[i] = cnt;
			}
			else
			{
				int pos = upper_bound(arr,arr+cnt,a[i],greater<int>()) - arr;
				arr[pos] = a[i];
				col[i] = pos+1;
			}
		}
		cout << cnt << endl;
		for(int i = 0;i < n;i++)
			cout << col[i] << " ";
		cout << endl;
	}
	return 0;
}
           

然后交一发，就有了：

？？？？？？？？？？？

我差的是你这1毫秒？

突然就被卡T了，找来找去不知道啥原因，就用scanf和printf试了一发

怀着疑惑的心情交了这一发：

OHHHHHHHHHHHH

这就过了？？

那我关了流再试试

于是我加上

ios::sync_with_stdio(0);

再试一发：

没有用，还是T，而且时间还是2001毫秒！

含着泪的结论

scanf大法好，在读入数据很大时scanf还是会比cin快好多的。

所以当本身的时间复杂度就很大时，并且读入数据也很大时，就用scanf吧，否则可能T了都不知道为啥。关于关流会变快，有时还会比scanf快这个说法是很玄学的，有些情况是会变快，但是在这道题上关流后一毫秒都没减少，所以还是老老实实用scanf吧（虽然cin方便TT）

终于碰到了一道卡cin的题，特此记录一下，涨知识了。