洛谷P1878|洛谷P1878 舞蹈课贪心堆洛谷P1878舞蹈课贪心堆

洛谷P1878 舞蹈课
贪心堆

1 #include 2 #define LL long long 3 #define GG int 4 #define For(i, j, k) for(register int i=j; i<=k; i++) 5 #define Dow(i, j, k) for(register int i=j; i>=k; i--) 6 using namespace std; 7 inline GG read() { 8GG x = 0, f = 1; 9char ch = getchar(); 10while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch = getchar(); } 11while(ch>='0'&&ch<='9') { x = x*10+ch-48; ch = getchar(); } 12return x * f; 13 } 14 void write(GG x) { 15if(x<0) putchar('-'), x = -x; 16if(x>9) write(x/10); 17putchar(x%10+48); 18 } 19 inline void writeln(GG x) { write(x); putchar('\n'); } 20 21 const int N = 2e5+11; 22 struct node{ 23int l, r, del; 24friend bool operator <(node a, node b) { 25if(a.del != b.del) return a.del > b.del; 26return a.l > b.l; 27} 28 }; 29 priority_queue Q; 30 int n, tot; 31 int val[N], vis[N], L[N], R[N]; 32 char s[N]; 33 34 inline void work() { 35while(!Q.empty()) { 36node p = Q.top(); Q.pop(); 37if(vis[p.l] || vis[p.r]) continue; 38vis[p.l] = 1; vis[p.r] = 1; 39L[++tot] = p.l; R[tot] = p.r; 40 41int l = p.l-1, r = p.r+1; 42while(l>=1 && vis[l]) --l; 43while(r<=n && vis[r]) ++r; 44if(l>=1 && r<=n && s[l]!=s[r]) 45Q.push((node){l, r, abs(val[l]-val[r]) }); 46} 47 } 48 49 int main() { 50n = read(); 51scanf("%s", s+1); 52For(i, 1, n) val[i] = read(); 53For(i, 1, n-1) 54if(s[i] != s[i+1]) 55Q.push((node){i, i+1, abs(val[i]-val[i+1])} ); 56work(); 57writeln(tot); 58For(i, 1, tot) { 59write(L[i]); putchar(' '); writeln(R[i]); 60} 61 }

【洛谷P1878|洛谷P1878 舞蹈课贪心堆】转载于:https://www.cnblogs.com/third2333/p/8476276.html