圖文不符,所以看不到也沒差

d244: 一堆石頭:

內容:

可愛的潘潘有著一堆石頭,每顆石頭上面都有一個正整數編號。接著,她又利用複製機器把每顆石頭都複製了兩個,而編號當然跟原來那個一樣。

可是有一天,她不小心掉了一顆石頭,現在她想要找出她掉的那一顆石頭的編號。

輸入說明:

只有一筆測資給你她現在所擁有的石頭的編號,用空格分開。

當然,個數一定是三的倍數減一個。

輸出說明:

輸出她掉的那一顆石頭的編號。

範例輸入:

9 8 6 9 8 2 3 5 2 1 6 8 1 5 1 2 3 3 5 9

範例輸出:

6

RE code:

#include <stdio.h>
int pcs[2000005]={0};//數量 
int main(){
	int tmp;
	while(scanf("%d",&tmp)!=EOF){
		pcs[tmp]++;
	}
	for(int i=1;i<=2000000;i++){
		if(pcs[i]==2)printf("%d",i);
	}
}

AC code:

想法:

因為題目未給定石頭數量,很難決定要開多大的陣列,所以用了 Vector 。存完石頭編號後就 sort 一下,然後依序檢查第 i 顆跟第 i+2 顆編號一不一樣,不一樣的話就輸出編號。時間複雜度為 O(n) 。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector <int> num;
	long long tmp;
	while(cin>>tmp){
		num.push_back(tmp);
	}
	sort(num.begin(),num.end());
	for(int i=0;i<num.size();i++){
		if(num[i]==num[i+2])i = i + 2;
		else {
			cout<<num[i]<<'\n';
			break;
		}
	}
	return 0;
}

pixiv