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中的所有相邻数,离这个中位数的距离是最短的。然后再求多一次所有相邻数与这个中位数的差,再求和。每一个数都是这样求,再从这些和里面找出最少的一个就是答案。

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

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

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; #define LL long long
#define pb push_back
const int maxn = 1e5 + ;
vector<int> adj[maxn]; // adj[i]: 数值为i的数中相邻的两个不等于i的数
LL sum, ans; // sum: 每个数相邻数之差的总和; ans: 最后答案
LL adjsum[maxn], adjminsum[maxn]; // adjsum[i]:数值为i的数相邻之间的差 adjminsum[i]: 数值为i的数相邻之间的差的最小值
int a[maxn]; // 原始序列 int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= m; i++)
scanf("%d", a+i);
for (int i = ; i <= m; i++)
{
if (i != && a[i-] != a[i])
adj[a[i]].pb(a[i-]);
if (i != m && a[i+] != a[i])
adj[a[i]].pb(a[i+]);
}
sum = ;
memset(adjsum, , sizeof(adjsum));
for (int i = ; i <= n; i++)
{
if (adj[i].size())
{
sort(adj[i].begin(), adj[i].end()); // 排序以便找出中位数
for (int j = ; j < adj[i].size(); j++)
adjsum[i] += (i >= adj[i][j] ? i-adj[i][j] : adj[i][j]-i);
sum += adjsum[i];
}
}
sum /= ; // 由于每个数相邻数之差的总和算了两遍,除以2刚好只算了一次
ans = sum;
memset(adjminsum, , sizeof(adjminsum));
for (int i = ; i <= n; i++)
{
if (adj[i].size())
{
int mid = adj[i].size() / ;
for (int j = ; j < adj[i].size(); j++)
adjminsum[i] += (adj[i][mid] >= adj[i][j] ? adj[i][mid]-adj[i][j] : adj[i][j]-adj[i][mid]);
ans = min(ans, sum-adjsum[i]+adjminsum[i]);
}
}
printf("%lld\n", ans);
for (int i = ; i <= n; i++) // 清空
adj[i].clear();
}
return ;
}
上一篇:codeforces A. Kitahara Haruki's Gift 解题报告


下一篇:把可执行jar打包成exe文档