題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長(zhǎng)度為 $n$ 的數(shù)列，每個(gè)數(shù)字有一個(gè)顏色，如果是藍(lán)色，每次操作則可以減一；如果是紅色，每次操作則可以加一。

問(wèn)有限次操作后，能否將數(shù)組變?yōu)橐粋€(gè)長(zhǎng)度為 $n$ 的排列。

題目分析：第一次做的時(shí)候用 multiset 亂搞過(guò)了，但感覺不算正解，看了題解后發(fā)現(xiàn)這不就是一個(gè)經(jīng)典的貪心套路：區(qū)間和數(shù)字的最大匹配問(wèn)題。

先將區(qū)間按左端點(diǎn)排序，再將數(shù)字從小到大排序，然后用優(yōu)先隊(duì)列控制區(qū)間右端點(diǎn)是否過(guò)期就可以了。

代碼：

// Problem: D. Blue-Red Permutation // Contest: Codeforces - Codeforces Round #753 (Div. 3) // URL: https://codeforces.com/contest/1607/problem/D // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; struct Node {int l,r;bool operator<(const Node& t)const {return r>t.r;} }node[N]; int a[N]; char s[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {int n;read(n);for(int i=1;i<=n;i++) read(a[i]);scanf("%s",s+1);for(int i=1;i<=n;i++) {if(s[i]=='B') node[i]={1,a[i]};else node[i]={a[i],n};}sort(node+1,node+1+n,[&](Node a,Node b) {return a.l<b.l;});bool flag=true;priority_queue<Node>q;int p=1;for(int i=1;i<=n;i++) {while(p<=n&&node[p].l<=i) q.push(node[p++]);int can=false;while(q.size()) {Node cur=q.top();q.pop();if(cur.r>=i) {can=true;break;}}flag&=can;}puts(flag?"YES":"NO");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1607D Blue-Red Permutation(贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。