poj 1084 Brainman

题目链接:http://poj.org/problem?id=1804

思路:

序列的逆序数即为交换次数,所以求出该序列的逆序数即可。

根据分治法思想,序列分为两个大小相等的两部分,分别求子序列的逆序数;对于右子序列中的每一个数,求出左序列中大于它的数的数目,计算的和即为解。

另外,使用Merge排序时,可以很容易求得对于右子序列中的每一个数,左序列中大于它的数的数目。

代码:

#include <stdio.h>
#include <limits.h>

long long Count = 0;
const int MAX_N = 1000 + 10;
long long A[MAX_N], L[MAX_N], R[MAX_N];

void Merge(long long A[], int p, int q, int r)
{
    int i, j, k;

    int n1 = q - p + 1;
    int n2 = r - q;

    for (int i = 0; i < n1; ++i)
        L[i] = A[p + i];
    for (int j = 0; j < n2; ++j)
        R[j] = A[q + j + 1];

    i = j = 0;
    k = p;
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;

    while (k <= r)
    {
        if (L[i] > R[j])
        {
            A[k++] = R[j++];
            Count += n1 - i;
        }
        else
            A[k++] = L[i++];
    }
}

void Merge_Sort(long long A[], int p, int q)
{
    int r = (p + q) / 2;

    if (p < q)
    {
        Merge_Sort(A, p, r);
        Merge_Sort(A, r + 1, q);
        Merge(A, p, r, q);
    }
}

int main()
{
    int n;
    int Scenario = 0;

    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int Num;

        scanf("%d", &Num);

        Count = 0;
        Scenario++;
        for (int i = 0; i < Num; ++i)
            scanf("%lld ", &A[i]);

        Merge_Sort(A, 0, Num - 1);
        printf("Scenario #%d:\n%lld\n\n", Scenario, Count);
    }

    return 0;
}
时间: 10-08

poj 1084 Brainman的相关文章

poj 1084 Square Destroyer dlx解重复覆盖

分析: 将问题转化为重复覆盖问题,DancingLink解决. 代码: //poj 1084 //sep9 #include <iostream> using namespace std; const int maxN=10024; const int maxL=128; int L[maxN],R[maxN],U[maxN],D[maxN]; int C[maxN],H[maxN]; int S[maxN],A[maxN],X[maxN]; bool makeup[maxL][maxL];

POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

Brainman Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 10575   Accepted: 5489 Description BackgroundRaymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just b

【POJ 1084】 Square Destroyer

[题目链接] http://poj.org/problem?id=1084 [算法] 迭代加深 [代码] #include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #inclu

POJ 1840 Brainman(逆序对数)

题目链接:http://poj.org/problem?id=1804 题意:给定一个序列a[],每次只允许交换相邻两个数,最少要交换多少次才能把它变成非递降序列. 思路:题目就是要求逆序对数,我们知道,求逆序对最典型的方法就是树状数组,但是还有一种方法就是Merge_sort(),即归并排序.实际上归并排序的交换次数就是这个数组的逆序对个数,归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序,然后再将这两半合并起来.在合并的过程中(设l<=i<=mid

[DLX重复覆盖] poj 1084 Square Destroyer

题意: n*n的矩形阵(n<=5),由2*n*(n+1)根火柴构成,那么其中会有很多诸如边长为1,为2...为n的正方形,现在可以拿走一些火柴,那么就会有一些正方形被破坏掉. 求在已经拿走一些火柴的情况下,还需要拿走至少多少根火柴可以把所有的正方形都破坏掉. 思路: 对于每个位置遍历所有可能的边长,确定这个边长下的正方形的边对应的都是数字几,并且把正方形从1开始编号. 然后根据编号,把正方形和数字建边记录方便下面建图. 然后以火柴棍为行,正方形为列,建立dancing link 然后求解. 这里

POJ 1084

WA了好久,第一次用重覆盖的模型做题.感觉这题有个陷阱,那就是当去掉某些边后,若因为这个边去掉而被破环的正方形还存在,那么就会造成覆盖不完全,WA. 所以,在去掉边后,必定有些正方形是不存在的,须重新计算.另外,计算一个正方形有哪些边也很困难. #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int

[DLX反复覆盖] poj 1084 Square Destroyer

题意: n*n的矩形阵(n<=5),由2*n*(n+1)根火柴构成,那么当中会有非常多诸如边长为1,为2...为n的正方形,如今能够拿走一些火柴,那么就会有一些正方形被破坏掉. 求在已经拿走一些火柴的情况下.还须要拿走至少多少根火柴能够把全部的正方形都破坏掉. 思路: 对于每一个位置遍历全部可能的边长,确定这个边长下的正方形的边相应的都是数字几,而且把正方形从1開始编号. 然后依据编号,把正方形和数字建边记录方便以下建图. 然后以火柴棍为行,正方形为列,建立dancing link 然后求解.

POJ 1804 Brainman(归并排序)

传送门 Description Background Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to

(中等) POJ 1084 Square Destroyer , DLX+可重复覆盖。

Description The left figure below shows a complete 3*3 grid made with 2*(3*4) (=24) matchsticks. The lengths of all matchsticks are one. You can find many squares of different sizes in the grid. The size of a square is the length of its side. In the