CodeForces1154E-蒲公英云

CodeForces1154E

CodeForces1154E
题意就是有两个教练,每个教练轮流操作,每次操作会选取所有未被选取的学生中能力值最高的那一个并把这个学生向左向右各\(k\)个学生选走.
如果不足\(k\)个就全部选走.两个教练轮流选取,直到所有学生都被选走为止.输出最后每个学生被哪一个教练选走了,设先选人的教练为\(1\),另一个为\(2\).
如果说直接按照题意模拟,复杂度是\(O(n^2)\)的,面对\(n \le 2\times 10^5\)的数据规模显然无能为力.
我们考虑,如果说没有向左向右分别再选\(k\)个的话,可以直接用堆维护,每次取堆顶就行了.那么加上这一步还能否用堆来维护呢?
答案似乎是可以的,如果我们试着用堆去维护,那么由于这题特殊的操作,我们需要同时在堆里维护每个数字的位置.
这样一个显然的思路就是在堆里压入一些\(pair\),由于\(pair\)的比较默认是以第一维,也就是\(first\)为第一关键字的,所以我们不需要重载运算符.
那么压入\(pair\)之后呢?有一个非常明显的问题是一个学生被选走了,但它可能还在堆里,以后如果再取堆顶可能会取到他.这个问题并不能处理,打标记就可以解决.那么这个标记怎么打呢?
如果每次都直接\(for\)一遍,显然就\(TLE\)了对叭.考虑如何优化这个标记的复杂度.
显然,每个学生只会被选取一次,换言之,其实我们的标记对每个学生只打一次就够了,而这样的复杂度显然是对的.
那么就着手考虑如何避免重复.一个比较自然的想法是维护每个学生向左向右第一个没被选取的学生的位置.
到了这里,思路就开阔许多了.这个东西你可以双向链表维护,可以并查集维护,也可以直接维护每个数字的前驱后继,每次选取学生后更新就行了.
我们开两个堆,每次选走一个学生就把被选走的压入第二个堆里,取堆顶之前,先判断如果两个堆的堆顶相等,那么说明现在的堆顶我们已经选走了,不断弹出即可.
这里第二个堆其实就相当于标记的作用.
这样的复杂度…我不太会分析,但是你只会把每个学生都遍历一遍,所以复杂度是正确的,又因为堆的存在,所以总复杂度大概是\(O(n log_2 n)\)?不太清楚,反正\(O(\:能\:过\:)\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 2e5 + 100 ; priority_queue < pii > q , d ; int n , k , v[N] , pre[N] , suf[N] ; int cnt1 , cnt2 , pos1 , pos2 ; bool coach , bel[N] ; signed main (int argc , char * argv[] ) { n = rint () ; k = rint () ; coach = false ; rep ( i , 1 , n ) { v[i] = rint () ; pre[i] = i - 1 ; suf[i] = i + 1 ; q.push ( { v[i] , i } ) ; } while ( ! q.empty () ) { while ( ! d.empty () && ! q.empty () && d.top () == q.top () ) d.pop () , q.pop () ; if ( q.empty () ) break ; pii tmp = q.top () ; pos1 = pos2 = tmp.Y ; for (cnt1 = 1 , pos1 = suf[pos1] ; cnt1 <= k && pos1 ; ++ cnt1 , pos1 = suf[pos1]) d.push ( { v[pos1] , pos1 } ) , bel[pos1] = coach ; for (cnt2 = 1 , pos2 = pre[pos2] ; cnt2 <= k && pos2 ; ++ cnt2 , pos2 = pre[pos2]) d.push ( { v[pos2] , pos2 } ) , bel[pos2] = coach ; pre[pos1] = pos2 ; suf[pos2] = pos1 ; bel[tmp.Y] = coach ; coach ^= 1 ; q.pop () ; } rep ( i , 1 , n ) printf ("%d" , ((int)bel[i]) + 1 ) ; system ("pause") ; return 0 ; }