UVa 10963

題目

http://domen111.github.io/UVa-Easy-Viewer/?10963

再東西向上有一群南北向的裂縫，對於每群裂縫我們可以把他們南北向任意移動

當所有裂縫的高度都相同時，裂縫就不存在了

現在給你每個裂縫的 $(y_1,y_2)$ ，求是否可以將裂縫補齊

想法

題目的意思其實就是因為可以任意移動，只要所有的裂縫高度都相同，那裂縫就能補齊

那麼我們只需要判斷是不是所有的高度都相同即可

拿一個變數去紀錄有出現過的高度，當有裂縫的高度跟他不同時，答案就會是 no ，所有高度都相同時為 yes

Code

#include<iostream>
#include<cmath>
using namespace std;
int n,m;
int main(){
	cin>>n;
	bool out=false;
	while(n--){
		if(out) cout<<"\n";
		else out=true;
		cin>>m;
		int cnt=-1; // 紀錄高度
		bool done=true;
		for(int i=0,x,y ; i<m ; i++){
			cin>>x>>y;
			if(cnt==-1) cnt=abs(x-y);
			else if(cnt!=abs(x-y))
				done=false;
		}
		if(done)
			cout<<"yes\n";
		else
			cout<<"no\n";
	}
	return 0;
}

時間複雜度分析

每筆測資輸入與計算高度時間複雜度為 $O(m)$

每筆測資總時間複雜度為 $O(m)$