CodeForces|CodeForces 980 C Posterized CodeForces980CPosterized

Posterized
题意：将[0,255] 分成若干段，每一段的长度最多为k, 每一个数只能被放进一个段里，然后每一段的数组都可以被这一段最小的数字表示，求最小的字典序。
题解：每次一个访问到一个数没被放到段里时，就在不破环前面分好段的情况下，尽可能将这个数分到前面段里去。然后将路上的点全部分到这段里。不要去去现在处理的这个数的后面的区域。
如k = 10; 现在有一个序列为 1， 11 那么如果你每次都从头开始染长度k的话，那么答案就是 0, 10，但是如果你每次就染到目前的点，不去管这个点之后的数，那么就会有更优的情况就是 0，2。

代码：

文章图片

文章图片

1 #include 2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 #define max3(a,b,c) max(a,max(b,c)) 12 #define min3(a,b,c) min(a,min(b,c)) 13 typedef pair pll; 14 const int INF = 0x3f3f3f3f; 15 const LL mod = 1e9+7; 16 const int N = 1e5+10; 17 int a[N], to[N]; 18 int n, m; 19 void ss(int u, int v){ 20for(int j = u; j <= v; j++){ 21to[j] = u; 22} 23 } 24 int main(){ 25///Fopen; 26scanf("%d%d", &n, &m); 27for(int i = 1; i <= n; i++) 28scanf("%d", &a[i]); 29for(int i = 0; i <= 256; i++) to[i] = -1; 30int t; 31for(int i = 1; i <= n; i++){ 32if(to[a[i]] != -1) a[i] = to[a[i]]; 33else { 34t = a[i]; 35int b = a[i] - m + 1; 36if(b < 0) b = 0; 37while(b < a[i]){ 38if(to[b] == -1) break; 39if(a[i]-to[b]+1 > m) b++; 40else break; 41} 42ss(b, a[i]); 43a[i] = to[a[i]]; 44} 45} 46for(int i = 1; i <= n; i++) 47printf("%d%c", a[i], " \n"[i==n]); 48return 0; 49 }

View Code 【CodeForces|CodeForces 980 C Posterized】
转载于:https://www.cnblogs.com/MingSD/p/9017309.html