codeforces B. Trees in a Row 解题报告

题目链接：http://codeforces.com/problemset/problem/402/B

题目意思：给出n个数和公差k，问如何调整使得a_i + 1 - a_i = k。（1 ≤ i < n），即等差数列，求出最少的调整次数。（调整的操作包括向一个数添加或者减少某个数，使得后一个数-前一个数 = 公差）。

方法一：

对于每一个数ai，求出以ai为基准，在ai之前和在ai之后不满足等差数列的个数。直到扫描整个序列结束，选出个数最少的，，即调整的次数最少，然后再一次扫描整个序列，算出每一个数需要调整的大小即可。要注意的是，每一个需要调整的数调整之后都需要满足>= 1！！

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 const int maxn =  + ;

 int a[maxn], rea[maxn][];  // a:原始输入序列 rea:保存需要调整的数的调整大小

 char ch[maxn];

 int main()

 {

     int d, n, i, j;

     while (scanf("%d%d", &n, &d) != EOF)

     {

         for (i = ; i <= n; i++)

             scanf("%d", &a[i]);

         int ans = maxn, cnt = ;

         int flag, rec = ;

         for (i = ; i <= n; i++)

         {

             flag = ;

             for (j = i-; j >= ; j--)  // 扫描以ai为基准的前面的数

             {

                 if (a[i] - (i-j)*d != a[j])

                 {

                     if (a[i] - (i-j)*d >= )

                         cnt++;

                     else     // 调整后的数不满足 >= 1

                     {

                         flag = ;

                         break;

                     }

                 }

             }

             for (j = i+; j <= n && !flag; j++)  // 扫描以ai为基准的后面的数

             {

                 if (a[i] + (j-i)*d != a[j])

                  {

                      if (a[i] + (j-i)*d >= )

                         cnt++;

                      else

                       {

                           flag = ;

                           break;

                       }

                  }

             }

             if (cnt < ans && !flag)   // ans保存最少的调整次数

             {

                 ans = cnt;

                 rec = i;   // 记录当前得出最少调整数量的以第i个数为基准的下标

             }

             cnt = ;

         }

         int l = ;

         cnt = ;

         for (j = rec-; j >= ; j--)     // 前面开始调整

         {

             if (a[rec] - (rec-j)*d != a[j])

              {

                  cnt++;

                  if (a[rec] - (rec-j)*d > a[j])

                  {

                      ch[l] = '+';

                      rea[l][] = j;

                      rea[l][] = a[rec] - (rec-j)*d - a[j];

                  }

                  else

                  {

                      ch[l] = '-';

                      rea[l][] = j;

                      rea[l][] =  a[j] - (a[rec] - (rec-j)*d);

                  }

                 l++;

              }

         }

         for (j = rec+; j <= n; j++)  // 后面开始调整

         {

             if (a[rec] + (j-rec)*d != a[j])

             {

                 cnt++;

                 if (a[rec] + (j-rec)*d > a[j])

                 {

                     ch[l] = '+';

                     rea[l][] = j;

                     rea[l][] = a[rec] + (j-rec)*d - a[j];

                 }

                 else

                 {

                     ch[l] = '-';

                     rea[l][] = j;

                     rea[l][] = a[j] - (a[rec] + (j-rec)*d);

                 }

                 l++;

             }

         }

         printf("%d\n", l);

         for (i = ; i < l; i++)

             printf("%c %d %d\n", ch[i], rea[i][], rea[i][]);

     }

 }

方法二：

考虑到原始序列中每个数的范围是[1, 1000]。因此可以对a[1] 从 [1, 1000] 里依次取数，再根据公差算出对应的a[2]～a[n]的值，与输入序列的a[2] ～ a[n] 比较，累加不同的数cnt。直到a[1] 完全取尽[1, 1000]范围内的数。当然a[1]每取一个数，都有对应的cnt，求出最少的cnt还有对应的a[1]的值。最后根据最少cnt和a[1]，对初始序列不符合项进行更改。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 const int maxn =  + ;

 int a[maxn];

 int main()

 {

     int n, k, i, j;

     while (scanf("%d%d", &n, &k) != EOF)

     {

         for (i = ; i <= n; i++)

             scanf("%d", &a[i]);

         int p, tmp, cnt, mini;

         mini = maxn;

         for (i = ; i <= ; i++)

         {

             tmp = i, cnt = ;

             for (j = ; j <= n; j++)

             {

                 if (a[j] != tmp)

                     cnt++;

                 tmp += k;

             }

             if (cnt <= mini)

             {

                 mini = cnt;

                 p = i;

             }

         }

         printf("%d\n", mini);

         for (i = ; i <= n; i++)

         {

             if (p != a[i])

             {

                 if (p > a[i])

                     printf("+ %d %d\n", i, p-a[i]);

                 else

                     printf("- %d %d\n", i, a[i]-p);

             }

             p += k;

         }

     }

     return ;

 }

巴特西

codeforces B. Trees in a Row 解题报告

最新文章

热门文章