UVa-10763

掌握了新姿势

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<map>
 5 using namespace std;
 6 const int maxx=500010;
 7 int a[maxx],b[maxx];
 8 int main()
 9 {
10     //freopen("in.txt","r",stdin);
11     //freopen("out.txt","w",stdout);
12     int n;
13     while(~scanf("%d",&n)&&n)
14     {
15         multimap<int,int> m;
16         for(int i=1;i<=n;i++)
17         {
18             scanf("%d%d",&a[i],&b[i]);
19             m.insert(pair<int,int>(a[i],b[i]));
20         }
21         for(int i=1;i<=n;i++)
22         {
23             /*int num=m.count(b[i]);//超时做法
24             if(num==0) break;
25             multimap<int,int>::iterator it=m.find(b[i]);
26             int j;
27             for(j=1;j<=num;j++)
28             {
29                 if(it->second==a[i])
30                 {
31                     m.erase(it);
32                     break;
33                 }
34                 it++;
35             }
36             if(j>num) break;*/
37             pair<multimap<int,int>::iterator,multimap<int,int>::iterator> p;
38             p=m.equal_range(b[i]);
39             if(p.first==p.second) break;
40             else
41             {
42                 multimap<int,int>::iterator it;
43                 for(it=p.first;it!=p.second;it++)
44                 {
45                     if(it->second==a[i])
46                     {
47                         m.erase(it);
48                         break;
49                     }
50                 }
51                 if(it==p.second) break;
52             }
53         }
54         puts(m.empty()?"YES":"NO");
55     }
56 }

上面的做法太耗时了，下面的是借鉴别人的算法。

 1 //边读边判断
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<map>
 6 using namespace std;
 7 int main()
 8 {
 9     //freopen("in.txt","r",stdin);
10     //freopen("out.txt","w",stdout);
11     int n;
12     while(~scanf("%d",&n)&&n)
13     {
14         multimap<int,int> m;
15         for(int i=1;i<=n;i++)
16         {
17             int a,b;
18             scanf("%d%d",&a,&b);
19             multimap<int,int>::iterator it;
20             for(it=m.find(b);it!=m.end()&&it->first==b;it++)
21             {
22                 if(it->second==a)
23                 {
24                     m.erase(it);
25                     break;
26                 }
27             }
28             if(it==m.end()||it->first!=b) m.insert(make_pair(a,b));
29         }
30         puts(m.empty()?"YES":"NO");
31     }
32 }