题意:将[0,255] 分成 若干段, 每一段的长度最多为k, 每一个数只能被放进一个段里, 然后每一段的数组都可以被这一段最小的数字表示, 求最小的字典序。
题解:每次一个访问到一个数没被放到段里时, 就在不破环前面分好段的情况下, 尽可能将这个数分到前面段里去。然后将路上的点全部分到这段里。 不要去去现在处理的这个数 的后面的区域。
如k = 10; 现在 有一个序列为 1, 11 那么 如果你每次都从头开始染长度k的话, 那么答案就是 0, 10, 但是如果你每次就染到 目前的点, 不去管这个点之后的数, 那么就会有更优的情况就是 0,2。
代码:
1 #include2 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<<110 #define rson m+1,r,rt<<1|111 #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){20 for(int j = u; j <= v; j++){21 to[j] = u;22 }23 }24 int main(){25 ///Fopen;26 scanf("%d%d", &n, &m);27 for(int i = 1; i <= n; i++)28 scanf("%d", &a[i]);29 for(int i = 0; i <= 256; i++) to[i] = -1;30 int t;31 for(int i = 1; i <= n; i++){32 if(to[a[i]] != -1) a[i] = to[a[i]];33 else {34 t = a[i];35 int b = a[i] - m + 1;36 if(b < 0) b = 0;37 while(b < a[i]){38 if(to[b] == -1) break;39 if(a[i]-to[b]+1 > m) b++;40 else break;41 }42 ss(b, a[i]);43 a[i] = to[a[i]];44 }45 }46 for(int i = 1; i <= n; i++)47 printf("%d%c", a[i], " \n"[i==n]);48 return 0;49 }