首页 > ACM题库 > HDU-杭电 > hdu 4108 Harmony待解决[解题报告]C++
2015
04-16

hdu 4108 Harmony待解决[解题报告]C++

Harmony

问题描述 :

Ali is given an array, which is a permutation of {1, 2, 3 … , n}. He thinks that only the increasing sequence is harmony, so he wants to change the sequence into a harmony one. But the only operation he can use is: Choosing a contiguous subsequence {A[i], A[i + 1]…A[j]} and do a random shuffling on it. (Random shuffle means that every permutation will appear with equal possibility)
So, what’s the expected number of operations when using the best strategy?

输入:

The input consists several testcases.
First line, an integer N (0 < N <= 50) denoting the length of this array.
In the next line there are N integers, representing a permutation.

输出:

The input consists several testcases.
First line, an integer N (0 < N <= 50) denoting the length of this array.
In the next line there are N integers, representing a permutation.

样例输入:

5
2 1 3 5 4

样例输出:

4.0000000000


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count