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