?

?

HDU6301.Distinct Values

?

這個題就是給你區間要求區間內的數都不相同，然后要求是字典序最小，直接貪心走一遍，但是自己寫的時候，思路沒有錯，初始化寫挫了。。。

將區間按左端點小的排序，如果相同就按右端點大的排序，因為右端點大的肯定滿足右端點小的。然后直接標記數組記錄當前區間已有的數，然后將沒有的數字填到里面。注意初始化就可以了。

?

代碼:

1 //1004-6301-字典序最小的序列，貪心策略，標記當前段出現過的 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<cstdlib> 8 #include<cassert> 9 using namespace std; 10 typedef long long ll; 11 const int maxn=1e5+10; 12 13 struct node{ 14 int l,r; 15 bool operator< (const node &a) const { 16 if(l==a.l) return r>a.r; 17 else return l<a.l; 18 } 19 20 }a[maxn]; 21 22 int cnt[maxn],ans[maxn]; 23 int main() 24 { 25 int t; 26 scanf("%d",&t); 27 while(t--){ 28 int n,m;scanf("%d%d",&n,&m); 29 memset(cnt,0,sizeof(cnt)); 30 memset(ans,0,sizeof(ans)); 31 for(int i=0;i<m;i++) 32 scanf("%d%d",&a[i].l,&a[i].r); 33 sort(a,a+m); 34 for(int i=a[0].l;i<=a[0].r;i++) 35 ans[i]=i-a[0].l+1; 36 int num,L=a[0].l,R=a[0].r; 37 for(int i=1;i<m;i++){ 38 if(a[i].r<=R) continue; 39 num=1; 40 if(a[i].l<=R){ 41 for(int j=a[i].l;j<=R;j++) 42 cnt[ans[j]]=i; 43 for(int j=R+1;j<=a[i].r;j++){ 44 while(cnt[num]==i)++num; 45 ans[j]=num++; 46 } 47 L=a[i].l,R=a[i].r; 48 } 49 else{ 50 for(int j=a[i].l;j<=a[i].r;j++) 51 ans[j]=num++; 52 L=a[i].l,R=a[i].r; 53 } 54 } 55 for(int i=1;i<n;i++){ 56 if(ans[i])printf("%d ",ans[i]); 57 else printf("1 "); 58 } 59 if(ans[n])printf("%d\n",ans[n]); 60 else printf("1\n"); 61 } 62 return 0; 63 }

?

轉載于:https://www.cnblogs.com/ZERO-/p/9385544.html

總結

以上是生活随笔為你收集整理的HDU 6301.Distinct Values-贪心、构造字典序最小的数列 (2018 Multi-University Training Contest 1 1004)...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。