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[s.ret(s3)] >= 1){
49                 m[s.ret(s3)]--;
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