10763 Foreign Exchange 解题心得
先上原题地址 ：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82547#problem/D
看过题目之后我的想法就是：
把输入的数据一个一个来看——得到一组数据，判断它的逆序出现了几次，如果出现了就把逆序出现的次数减一，如果没出现就把这个序的次数加一，看所有序的出现次数是不是全为0；如果是就所有配对，yes、
至于要标记一组有序对的出现次数，又一次想到了map，因为是2个数据组合成一个有序对，所以用一个结构体将他们组成一个整体，map<结构体，int>。
然而想要结构体作为map的左参数，这就需要这个结构体定义了<操作符，而且还要满足map的判断2个结构体不相等的机制（a<b,b<a 有且仅有一个成立 ->a b不相等 //否则a b相等）
这样就可以写代码了
1 #include<iostream>
2 #include<map>
3 #include<cstdio>
4 using namespace std;
5
6
7 struct st
8 {
9 int local;
10 int target;
11 void read()
12 {
13 scanf("%d""%d", &local, &target); //数据比较多 用scanf节省了300ms
14 /*cin >> local >> target;*/
15 }
16 bool operator <(const st b) const //一定要加const
17 {
18 if (b.local == local&& target == b.target) return false; //a<b有且只有一个成立
19 if (b.local == local&& target <b.target ) return true;
20 if (b.local == local&& target > b.target) return false;
21 if (local<b.local)return true;
22 /* if (b.local < local&&b.target < target) return true;
23 if (b.local < local&&b.target == target) return true;
24 if (b.local < local&&b.target > target) return true;*/
25 if ( local >b.local) return false;
26 /*if (b.local > local&&b.target == target) return false;
27 if (b.local > local&&b.target > target) return false;
28 if (b.local > local&&b.target < target) return false;*/
29 }
30 st & ret(st &s3)
31 {
32 s3.local = target;
33 s3.target = local;
34 return s3;
35 }
36
37 }s;
38
39 map<st, int> m;
40 st s3;
41 int main()
42 {
43 int n;
44 while (cin >> n&&n != 0){
45 m.clear();
46 while (n--){
47 s.read();
48 if (m >= 1){
49 m--;
50 }
51 else{
52 m++;
53 }
54 }
55 bool flag = 0;
56 map<st, int>::iterator it;
57 map<st, int>::iterator end = m.end();
58 for (it = m.begin(); it !=end ; it++){
59 if ((*it).second != 0){
60 flag = 0;//puts("NO");
61 break;
62 }
63 flag = 1;//puts("YES");
64 }
65 if (flag == 1) puts("YES");
66 else puts("NO");
67 }
68 return 0;
69 }
View Code
页:
[1]