【CCF】找相反數

題目1相反數

時間限制:1秒空間限制:256MB

問題描述

有N個非零且各不相同的整數。請你編一個程式求出它們中有多少對相反數（a和?a為一對相反數）。

輸入格式

第一行包含一個正整數N。(1≤N≤500)。

第二行為N個用單個空格隔開的非零整數，每個數的絕對值不超過1000，保證這些整數各不相同。

輸出格式

隻輸出一個整數，即這N個數中包含多少對相反數。

輸入樣例

5

123-1-2

輸出樣例

2

① 連結清單法

#include<iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;

class Node{
	public:
		int data;
		Node* next;
		Node(){
			next = NULL;
		}
};

class LinkedList{
private:

	Node* head;
	Node* last;
	int len ;
public:
	LinkedList(){
		head = NULL;
		last = NULL;
		len = 0;
	}
	~LinkedList(){
		Node*p=head;
		Node*q;
		while(p){
			q = p;
			p=p->next;
			delete q;
		}
	}
	void add(int element){
		if(head){
			last->next=new Node();
			last->next->data=element;
			last = last->next;
			len ++;
		}
		else{
			head = new Node();
			head->data = element;
			last = head;
			len ++;
		}
	}
	void remove(int i){
		Node* p=head;
		Node* q=NULL;
		if(i==0){
			q=p;
			head=head->next;
			delete q;
			return;
		}
		while(i--){
			q=p;
			p=p->next;
		}
		if(p->next){
			Node* m = p;
			p=p->next;
			q->next = p;
			delete m;
		}
		else{
			last = q;
			last->next=NULL;
			delete p;
		}
	}
	void display(){
		Node* p = head;
		while(p){
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;
	}
	Node* gethead(){
		return head;
	}
};

int main(){
	LinkedList pn;//正數
	LinkedList nn;//負數
	srand((unsigned int)time(0));
	int tn,n;
	cin>>tn;
	while(tn--){
		n=rand()%1000 * ((rand()%2==0)?1:-1);
		cout<<n<<" ";
	//	cin>>n;
		if(n>0){
			pn.add(n);
		}
		else{
			nn.add(-n);
		}
	}
	cout<<endl;
	Node* pn_head = pn.gethead();
	Node* nn_head;
	int i,amout=0;
	while(pn_head){
		nn_head = nn.gethead();
		i = 0;
		while(nn_head){
			if(nn_head->data==pn_head->data){
				cout<<nn_head->data<<" -"<<pn_head->data<<endl;
				amout++;
				nn.remove(i);
				break;
			}
			i++;
			nn_head=nn_head->next;
		}
		pn_head=pn_head->next;
	}
	cout<<amout<<endl;
	return 0;
}
           

② 集合法(參考位址：http://zhidao.baidu.com/link?url=goVljwhiSGnJhCyU39b7uuPe7yB95QxtRVIqTPCTpzZls-UMzfJShm0tW2sxHtrd895mj8p7mWOPPhtqzujPt7PvtEVwPyUfv_OueeZKF7K)

#include<iostream>
#include<set>
using namespace std;
int main(){
	int N,n;
	set<int> s;
	cin>>N;
	int i = N;
	while(i--){
		cin>>n;
		if(n>=0){
			s.insert(n);
		}
		else{
			s.insert(-n);
		}
	}
	cout<<(N-s.size())<<endl;
	return 0;
}