codeforces 340C Tourist Problem

September 4, 2013
CodeForces

link:http://codeforces.com/problemset/problem/340/C

开始一点也没思路，赛后看别人写的代码那么短，可是不知道怎么推出来的啊！

后来明白了。

首先考虑第一个数字，就是和0想减的内个。那么剩下的n-1个数字有(n-1)!个排列方式。所以呢，在n!个式子里面，第一个位置的和就是：a1 * (n-1)! + a2 * (n-1)! + …… + an * (n-1)!；

然后考虑其它位置：对于ai , aj . 并且相邻。那么剩下 n - 2 个数字，这些数字有 (n-2)!个排列方式，然后把相邻的 ai aj 插入，有 n-1 种插入方式，所以呢，一共有 (n-1) * (n-2)! = (n-1)! 个方式，其它位置的和就是：(n-1)! * fabs(ai - aj) 【i != j, 1 <= i, j <= n】

关键是第二个式子怎么求呢？好像很难得样子。可以找规律啊。比如，a1, a2 , a3, a4.

因为有绝对值，我可以先排序，先算正的，在 *2就行了。假设a1 > a2 > a3 > a4

设：

以a2结尾的ai - aj 的和是S2.

以a3……和是S3

。a4…………S4

那么：

S2 = a1 - a2

S3 = a1 - a3 + a2 - a3 = (a1 - a2 + a2 - a3) + a2 - a3 = S2 + 2 *（a2 - a3）

S4 = a1 - a4 + a2 - a4 + a3 - a4 = (a1 - a3 + a3 - a4) + (a2 - a3 + a3 - a4) + (a3 - a4) = S3 + 3 * (a3 - a4)

我们要求的就是S2 + S3 + S4。

没发现Si 可以递推么~

/*
 *       Filename:  tourist.cpp
 *        Created:  09/01/2013 09:14:49 AM
 *         Author:  liuxueyang (lxy), zypz457@sina.com
 *   Organization:  Hunnan University
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
using namespace std;
#define LL long long
int a[100009];
int main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    ios::sync_with_stdio(false);
    int n;
    while (~scanf("%d", &n)) {
        LL katusya = 0, tatusya = 0, safe = 0;
        for (int i = 0; i < n; scanf("%d",a+i), katusya+=a[i], ++i);
        sort(a, a + n);
        for (int i = 1; i < n; ++i)  {
            safe += (LL)i * (a[i]-a[i-1]);
            tatusya += safe;
        }
        tatusya *= 2;
        tatusya += katusya;
        LL touch = __gcd(tatusya, (LL)n);
        printf("%lld %lld\n", tatusya/touch, n/touch);
    }
        return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

比赛没做出来，但是觉得这道题目很好！

用动态规划的思想，很巧妙啊。

嗨，中村。

Read more