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

我就是我 2022-11-17 13:51 176阅读 0赞

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

然后交一发，就有了：  
![在这里插入图片描述][20210409213401837.png]

![在这里插入图片描述][20210409213454223.png]

？？？？？？？？？？？  
我差的是你这1毫秒？

突然就被卡T了，找来找去不知道啥原因，就用scanf和printf试了一发  
怀着疑惑的心情交了这一发：  
![在这里插入图片描述][20210409213618460.png]  
![在这里插入图片描述][20210409213643363.png]  
OHHHHHHHHHHHH  
这就过了？？  
那我关了流再试试  
于是我加上`ios::sync_with_stdio(0);`再试一发：  
![在这里插入图片描述][20210409213401837.png]  
没有用，还是T，而且时间还是2001毫秒！

### 含着泪的结论 ###

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

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

[Simone and graph coloring]: https://ac.nowcoder.com/acm/contest/12548/L
[20210409213401837.png]: /images/20221022/f3c45b5d219246d5a08a9aacb4691e96.png
[20210409213454223.png]: /images/20221022/0641d0481e3e4892a5d31e29abcc6d43.png
[20210409213618460.png]: /images/20221022/f3e9540268784c818e45471760e78e01.png
[20210409213643363.png]: /images/20221022/9ba43a832fe44370be5ad9631c5912ea.png