題意：長為n的串，給你m個區(qū)間，這些區(qū)間內(nèi)元素不重復，問這樣的串字典序最小為？

思路：用set保存當前能插入的元素，這樣就能直接插入最小元素了。對操作按l排序，因為排過的不用排，所以兩個指針L，R是一直右移的。L右移肯定是增加set中元素，R右移有兩種可能：一是L在R右邊，R只是負責趕路趕到操作區(qū)間；二是L在R左邊，那么R右移是在擴大區(qū)間，并且對數(shù)組中元素進行插入。

代碼：

#include<cstdio> #include<vector> #include<set> #include<queue> #include<cstring> #include<string> #include<cmath> #include<cstdlib> #include<algorithm> #define ll long long const int maxn = 100000+5; const int maxm = 100000+5; const int MOD = 1e7; const int INF = 0x3f3f3f3f; using namespace std; struct node{int l,r; }q[maxn]; bool cmp(node a,node b){return a.l == b.l? a.r < b.r : a.l < b.l; } int ans[maxn]; int main(){int T;int n,m;scanf("%d",&T);while(T--){memset(ans,0,sizeof(ans));scanf("%d%d",&n,&m);set<int> s;for(int i = 1;i <= n;i++){s.insert(i);}for(int i = 0;i < m;i++)scanf("%d%d",&q[i].l,&q[i].r);sort(q,q+m,cmp);for(int i = q[0].l;i <= q[0].r;i++){ans[i] = *s.begin();s.erase(ans[i]);}int L = q[0].l,R = q[0].r;for(int i = 1;i < m;i++){while(L < q[i].l){if(ans[L] != 0) s.insert(ans[L]);L++;}while(R < q[i].r){if(L > R){if(ans[R] != 0) s.insert(ans[R]);R++;}else{if(L == R){if(ans[R] == 0){ans[R] = *s.begin();s.erase(ans[R]);}else s.erase(ans[R]);R++;if(ans[R] == 0){ans[R] = *s.begin();s.erase(ans[R]);}else s.erase(ans[R]);}else{R++;if(ans[R] == 0){ans[R] = *s.begin();s.erase(ans[R]);}}}}}for(int i = 1;i <= n;i++){if(i != 1) printf(" ");if(ans[i] == 0) printf("1");else printf("%d",ans[i]);}printf("\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/KirinSB/p/9408749.html

總結(jié)

以上是生活随笔為你收集整理的hdu 6301 Distinct Values（贪心）题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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