Educational Codeforces Round 24 D. Multicolored Cars(set)

题目链接：Educational Codeforces Round 24 D. Multicolored Cars

题意：

给你n个数，和Alice选的数A，让你在这n个数中找一个数x，

使得对于第i个数，cnt[A]<=cnt[x],

题解：

set乱搞一下，每次将比cnt[A]小的数删掉就行了。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 
 5 const int N=1e6+7;
 6 
 7 struct Node
 8 {
 9     int x,cnt;
10     Node(int a=0,int b=0):x(a),cnt(b){}
11     bool operator<(const Node &b)const{return x<b.x;}
12 };
13 
14 int n,m,vis[N],cnt,x;
15 set<Node>st;
16 set<Node>::iterator IT;
17 int main()
18 {
19     scanf("%d%d",&n,&m);
20     F(i,1,n)
21     {
22         scanf("%d",&x);
23         if(x==m)
24         {
25             cnt++;
26             while(st.size()&&(*st.begin()).cnt<cnt)
27             {
28                 vis[(*st.begin()).x]=-1;
29                 st.erase(st.begin());
30             }
31         }
32         else
33         {
34             Node tmp;
35             if(vis[x]>0)
36             {
37                 IT=st.lower_bound(Node(x));
38                 tmp=*IT,st.erase(IT);
39                 tmp.cnt++,st.insert(tmp);
40             }
41             else if(vis[x]==0&&cnt==0)
42             {
43                 vis[x]=1,tmp=Node(x,1),st.insert(tmp);
44             }
45         }
46     }
47     if(st.size())printf("%d
",(*st.begin()).x);
48     else puts("-1");
49     return 0;
50 }

View Code