HDU6301 Distinct Values (多校第一场1004) (贪心) Distinct Values
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4869 Accepted Submission(s): 1659
Problem Description
Chiaki has an array of j holds.
Chiaki would like to find a lexicographically minimal array which meets the facts.
Chiaki would like to find a lexicographically minimal array which meets the facts.
Input
There are multiple test cases. The first line of input contains an integer 6.
Output
For each test case, output n integers denoting the lexicographically minimal array. Integers should be separated by a single space, and no extra spaces are allowed at the end of lines.
Sample Input
3
2 1
1 2
4 2
1 2
3 4
5 2
1 3
2 4
Sample Output
1 2
1 2 1 2
1 2 3 1 1
给出q个[l,r] 要求[l,r]范围内数字不重复 ,求字典序最小的满足q个要求的序列。
首先预处理出来覆盖每一个点的最左端点pre[i] ,用p从1开始 和 pre[i]比较,(因为当前区间是[pre[i], i], 上个区间是 [p, i-1] ) 如果 p < pre[i] , 就把[p, pre[i]-1] 的数都释放了(插入set还能用)如果 p > pre[i], 直接取set.begin().
1 // D 2 #include <bits/stdc++.h> 3 using namespace std; 4 #define rep(i,a,n) for (int i=a;i<n;i++) 5 #define per(i,a,n) for (int i=n-1;i>=a;i--) 6 #define pb push_back 7 #define mp make_pair 8 #define all(x) (x).begin(),(x).end() 9 #define fi first 10 #define se second 11 #define SZ(x) ((int)(x).size()) 12 typedef vector<int> VI; 13 typedef long long ll; 14 typedef pair<int,int> PII; 15 const ll mod=1000000007; 16 ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} 17 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} 18 // head 19 20 const int N=101000; 21 int _,n,m,pre[N],l,r,ret[N];//pre维护覆盖i的最左端点 22 int main() { 23 for (scanf("%d",&_);_;_--) { 24 scanf("%d%d",&n,&m); 25 rep(i,1,n+1) pre[i]=i; 26 rep(i,0,m) { 27 scanf("%d%d",&l,&r); 28 pre[r]=min(pre[r],l); 29 per(i,1,n) pre[i]=min(pre[i],pre[i+1]);//pre[i]是pre[i]和pre[i+1]的最小值 30 int pl=1;//从1开始 和覆盖每个点的最左端点pre[i]比较 31 set<int> val; 32 rep(i,1,n+1) val.insert(i);//维护最小可用的数 33 rep(i,1,n+1) { 34 //上个 [pl, i-1] 35 36 //当前 [pre[i], i] 37 while (pl<pre[i]) {//小于pre[i]的点的值 插入set 38 val.insert(ret[pl]); 39 pl++; 40 } 41 ret[i]=*val.begin();//不小于直接取最小的数放进去 42 val.erase(ret[i]);//删除刚放入的数 43 } 44 rep(i,1,n+1) printf("%d%c",ret[i]," "[i==n]); 45 } 46 }