Bumb
Time Limit: 20 Sec Memory Limit: 512 MBDescription
Input
Output
Sample Input
4
1 5 1 4Sample Output
5
HINT
Solution
首先，我们对于一个已知的k，可以O(n)得到Ans，这样就有60%了。
那么怎么做90%呢？老老实实写O(nlogn)是不可能的！模拟退火美滋滋！
传授一点人生的经验吧：写个对拍用于调参，由于这种题不能很单峰，显然温度变化设大一点比较容易正确，无限running + 卡时即可。
是的，没有错！BearChild就这样拿到了90%！
我们来考虑100%怎么做，显然复杂度O(n)。我们把( a[i - 1], a[i] ]看作若干个区间挂在数轴上。
然后考虑k：1->m对于答案的变化。显然可以记录cnt表示k包含的区间个数，以及sum和，这样就可以做完啦！
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 using namespace std; 11 typedef long long s64;12 13 const int ONE = 1000005;14 const s64 INF = 1e18;15 16 int n, m;17 int a[ONE];18 int Now, A;19 s64 Ans = INF;20 21 int get()22 {23 int res=1,Q=1;char c;24 while( (c=getchar())<48 || c>57 ) 25 if(c=='-')Q=-1; 26 res=c-48; 27 while( (c=getchar())>=48 && c<=57 )28 res=res*10+c-48; 29 return res*Q;30 }31 32 void TimeE()33 {34 if((double)clock() / CLOCKS_PER_SEC > 0.97)35 {36 printf("%lld", Ans);37 exit(0);38 }39 }40 41 s64 Get(int x, int y)42 {43 TimeE();44 if(x <= y) return y - x;45 return y + m - x;46 }47 48 s64 Judge(int k)49 {50 s64 res = 0;51 for(int i = 2; i <= n; i++)52 res += min(Get(a[i - 1], a[i]), 1 + Get(k, a[i]));53 Ans = min(Ans, res);54 return res;55 }56 57 double Random() { return rand() / (double)RAND_MAX;}58 void SA(double T)59 {60 Now = m / 2;61 while(T >= 1)62 {63 A = Now + (int)(T * (Random() * 2 - 1));64 if(A < 1 || A > m) A = T * Random();65 s64 dE = Judge(A) - Judge(Now);66 if(dE < 0) Now = A;67 T *= 0.92;68 }69 }70 71 int main()72 {73 n = get(); m = get();74 for(int i = 1; i <= n; i++)75 a[i] = get();76 if(n > 3000) { for(;;)SA(m); return 0;}77 78 for(int i = 1; i <= m; i++)79 Ans = min(Ans, Judge(i));80 81 printf("%lld", Ans);82 }
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std; 10 typedef long long s64;11 12 const int ONE = 1000005;13 const s64 INF = 1e18;14 15 int n, m;16 int a[ONE];17 int L[ONE];18 vector R[ONE];19 s64 Ans;20 21 int get()22 {23 int res=1,Q=1;char c;24 while( (c=getchar())<48 || c>57 ) 25 if(c=='-')Q=-1; 26 res=c-48; 27 while( (c=getchar())>=48 && c<=57 )28 res=res*10+c-48; 29 return res*Q;30 }31 32 int Get(int x, int y)33 {34 if(x <= y) return y - x;35 return y + m - x;36 }37 38 int main()39 {40 n = get(); m = get();41 for(int i = 1; i <= n; i++)42 a[i] = get();43 44 for(int i = 2; i <= n; i++)45 {46 Ans += Get(a[i - 1], a[i]);47 L[a[i - 1]]++, R[a[i]].push_back(a[i - 1]);48 }49 50 s64 sum = Ans, cnt = 0;51 52 for(int i = 2; i <= n; i++)53 if(a[i - 1] > a[i])54 sum -= m - a[i - 1], cnt++;55 56 for(int k = 2; k <= m; k++)57 {58 int len = R[k - 1].size();59 cnt = cnt + L[k - 2] - len;60 sum -= cnt;61 for(int i = 0; i < len; i++)62 sum += Get(R[k - 1][i], k - 1) - 1;63 Ans = min(Ans, sum);64 }65 66 printf("%lld", Ans);67 }