codeforces 433C. Ryouko's Memory Note 解题报告

题目链接：http://codeforces.com/problemset/problem/433/C

题目意思：一本书有 n 页，每页的编号依次从 1 到 n 编排。如果从页 x 翻到页 y，那么|x-y|页都需要翻到（联系生活实际就很容易理解的了）。接着有m pieces 的 information，第 i piece 的information 在第 a[i] 页。为了减少翻页的页数，允许把某一页的信息，完全搬到某一页上，这个操作只可以执行一次。问应该把哪一页的信息搬到某一页上，从而使得翻页次数最少。

比赛的时候完全没有思路，赛后想了一段时间也是如此。于是看了tutorial，以下是链接：

http://codeforces.com/blog/entry/12397

实不相瞒，我看这个也有点...看来我的理解能力真心有问题！！！直接看了一个人的AC代码，再加上输出变量终于完全明白了。

如果大家已经看明白链接里的解题思路，那么以下内容可以忽略。

/*****************************************

首先保存每一个数左右两边与该数直接相邻的数都有哪些（注意：如果相邻的数与该数相等，就不需要保存）。假设初始序列是： 1 2 3 4 3 2 。那么如果需要保存数 3 的相邻数，就是2 4 4 2，这里用到vector操作。接着求出这些相邻数与该数之差，每一个数都这样求，得出一个和为sum，注意：这个sum 对整个序列的两两紧挨的数的差是求了两次的！！！所以代码中sum 要除以 2。紧随着对于某一个数（x），它的相邻数进行从小到大的排序，这样是为了找出中位数。这个中位数表示对于x中的所有相邻数，离这个中位数的距离是最短的。然后再求多一次所有相邻数与这个中位数的差，再求和。每一个数都是这样求，再从这些和里面找出最少的一个就是答案。

****************************************/

别人的思路真是清晰，好佩服他们。以下是我看明白之后写的

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <vector>
 7 using namespace std;
 8 
 9 #define LL long long
10 #define pb push_back
11 const int maxn = 1e5 + 5;
12 vector<int> adj[maxn];  // adj[i]: 数值为i的数中相邻的两个不等于i的数
13 LL sum, ans;      // sum: 每个数相邻数之差的总和;   ans: 最后答案
14 LL adjsum[maxn], adjminsum[maxn];   // adjsum[i]：数值为i的数相邻之间的差 adjminsum[i]: 数值为i的数相邻之间的差的最小值
15 int a[maxn];    // 原始序列
16 
17 int main()
18 {
19     int n, m;
20     while (scanf("%d%d", &n, &m) != EOF)
21     {
22         for (int i = 1; i <= m; i++)
23             scanf("%d", a+i);
24         for (int i = 1; i <= m; i++)
25         {
26             if (i != 1 && a[i-1] != a[i])
27                 adj[a[i]].pb(a[i-1]);
28             if (i != m && a[i+1] != a[i])
29                 adj[a[i]].pb(a[i+1]);
30         }
31         sum = 0;
32         memset(adjsum, 0, sizeof(adjsum));
33         for (int i = 1; i <= n; i++)
34         {
35             if (adj[i].size())
36             {
37                 sort(adj[i].begin(), adj[i].end());   // 排序以便找出中位数
38                 for (int j = 0; j < adj[i].size(); j++)
39                     adjsum[i] += (i >= adj[i][j] ? i-adj[i][j] : adj[i][j]-i);
40                 sum += adjsum[i];
41             }
42         }
43         sum /= 2;   // 由于每个数相邻数之差的总和算了两遍，除以2刚好只算了一次
44         ans = sum;
45         memset(adjminsum, 0, sizeof(adjminsum));
46         for (int i = 1; i <= n; i++)
47         {
48             if (adj[i].size())
49             {
50                 int mid = adj[i].size() / 2;
51                 for (int j = 0; j < adj[i].size(); j++)
52                     adjminsum[i] += (adj[i][mid] >= adj[i][j] ? adj[i][mid]-adj[i][j] : adj[i][j]-adj[i][mid]);
53                 ans = min(ans, sum-adjsum[i]+adjminsum[i]);
54             }
55         }
56         printf("%lld
", ans);
57         for (int i = 1; i <= n; i++)     // 清空
58             adj[i].clear();
59     }
60     return 0;
61 }

codeforces 433C. Ryouko's Memory Note 解题报告

相关推荐