題意：
? ? ? 給你一個循環(huán)串，然后找到一個位置，使得從這個位置開始的整個串字典序最小。


思路：

? ? ? 最小表示法的建檔應(yīng)用，最小表示法很好理解，就點貪心的意思，一開始我們枚舉兩個起點i,j然后誰大誰往后移動，相等則比較下一個，這樣到最后取一個小的值就行了，時間復(fù)雜度是O(n)的，很好的小方法。

#include<stdio.h> #include<string.h>char str[10005];int GetMin(char *str) {int len = strlen(str);int i = 0 ,j = 1 ,k = 0;while(i < len && j < len && k < len){int t = str[(i+k)%len] - str[(j+k)%len];if(!t) k ++;else{t > 0 ? i = i + k + 1 : j = j + k + 1;if(i == j) j ++;k = 0;}}return i < j ? i : j; }int main () {int t;scanf("%d" ,&t);while(t--){scanf("%s" ,str);printf("%d\n" ,GetMin(str)+1);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj1509最小表示法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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