题目:

在数组被的少数独数字,如果前一个数字高于后面的数字,则立即简单单数字组成一个逆序对。输入一个屡次组,求来这个数组中的逆序对之总额P。并拿P对1000000007得到模的结果输出。
即输出P%1000000007

6262:流感传染

  • 查看
  • 提交
  • 统计
  • 提问

究竟时间限定: 
1000ms

内存限制: 
65536kB

描述
发相同批判好感人群住在网格状的宿舍区内,宿舍区为n*n的矩阵,每个格点为一个室,房间里或住人,也恐怕空着。在率先龙,有些房间里的人数得矣流感,以后每天,得流感的人口见面要该近邻传染上流感,(已经得病的匪更换),空房间不会见传。请输出第m天得流感的总人口。

输入
先是履行一个数字n,n不越100,表示有n*n的宿舍房。
搭下的n行,每行n个字符,’.’表示第一天该房间已着正常之食指,’#’表示该房空着,’@’表示第一上该室已着得流感的人口。
连片下的同一执行是一个整数m,m不超过100.

输出
出口第m天,得流感的食指

样例输入
5
….#
.#.@.
.#@..

#....
.....
4

样例输出
16

 1 #include<cstring>
 2 #include<iostream>
 3 using namespace std;
 4 int n,t,ans;
 5 int a[110][110];
 6 bool b[110][110];
 7 char d[110][110];
 8 int main() {
 9     cin>>n;
10     for(int i=1; i<=n; i++)
11         for(int j=1; j<=n; j++)
12         {
13             cin>>d[i][j];
14             if(d[i][j]=='.')
15                 a[i][j]=1;
16             else if(d[i][j]=='@')
17                 a[i][j]=0;
18             else
19                 a[i][j]=-1;//1表示健康,0表示患病 ,-1表示无人
20         }
21     cin>>t;
22     for(int k=2; k<=t; k++) 
23     {
24         memset(b,true,sizeof(b));
25         for(int i=1; i<=n; i++)
26             for(int j=1; j<=n; j++) 
27             {
28                 if(a[i][j]==0&&b[i][j]==true) 
29                 {
30                     if(a[i-1][j]==1 ) 
31                     {
32                         a[i-1][j]=0;
33                         b[i-1][j]=false;
34                     }
35                     if(a[i+1][j]==1 ) 
36                     {
37                         a[1+i][j]=0;
38                         b[i+1][j]=false;
39                     }
40                     if(a[i][j-1]==1 ) 
41                     {
42                         a[i][j-1]=0;
43                         b[i][j-1]=false;
44                     }
45                     if(a[i][j+1]==1 ) 
46                     {
47                         a[i][j+1]=0;
48                         b[i][j+1]=false;
49                     }
50                 }
51             }
52     }
53     for(int i=1; i<=n; i++)
54     for(int j=1; j<=n; j++)
55         if(a[i][j]==0)
56             ans++;
57     cout<<ans;
58     return 0;
59 }

 

 过程

….#
.#.@.
.#@..
#….
….. 2

…@#
.#@@@
.#@@.
#.@..
…..                 7

..@@#
.#@@@
.#@@@
#@@@.
..@..                12

 

.@@@#
.#@@@
.#@@@
#@@@@
.@@@.           16

输入描述:

问题保证输入的数组中绝非底平等之数字

数量范围:

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

示例1

输入

1,2,3,4,5,6,7,0

输出

7

思路分析(剑指offer):

       
看到是题材,我们的率先影响是各个扫描整个数组。没扫描到一个数组的下,逐个比该数字与它们背后的数字的高低。如果后的数字较它有点,则立刻有限独数字就是整合了一个逆序对。假设数组中含有n个数字。由于每个数字还要同O(n)之数字较,因此此算法的日复杂度为O(n^2)。

       
我们因为数组{7,5,6,4}为条例来分析统计逆序对的历程。每次扫描到一个数字的当儿,我们不以ta和后面的各级一个数字作比,否则日复杂度就是O(n^2),因此我们得设想优先比较单薄独相邻之数字。

                                                   
 统计 1 

(a) 把长也4底数组分解成稀只长为2的子数组;

(b) 把长为2底数组分解成稀只成都啊1之子数组;

(c) 把长也1底子数组 合并、排序并统计逆序对 ;

(d) 把长为2底子数组合并、排序,并统计逆序对;

     
 在上图(a)和(b)中,我们事先拿数组分解变成稀单长为2之子数组,再将当下有限独子数组分别拆成稀独长也1的子数组。接下来一边合并相邻的子数组,一边统计逆序对之数。在第一对长为1的子数组{7}、{5}中7可怜让5,因此(7,5)组成一个逆序对。同样于次对准长也1之子数组{6}、{4}中为生逆序对(6,4)。由于我们就统计了就有限针对子数组内部的逆序对,因此用拿这点儿对子数组 排序 如齐图(c)所示, 以免在后来的统计过程中又另行统计。

 
    接下我们统计两单长为2底子数组子数组之间的逆序对。合并子数组并统计逆序对的经过要下图要下图所出示。

     
我们先行用鲜单指针分别凭借为少数单子数组的最终,并每次比单薄独指针指向的数字。如果第一个子数组中之数字高于第二单数组中的数字,则成逆序对,并且逆序对之数等于第二独子数组中剩下数字之个数,如下图(a)和(c)所示。如果第一个数组的数字小于或顶第二只数组中的数字,则无做逆序对,如图b所出示。每一样次等比的当儿,我们且把于生之数字从后往前头复制到一个辅助数组中,确保 辅助数组(记为copy) 中之数字是与日俱增排序的。在将于生之数字复制到援手数组之后,把相应之指针向前移动一各项,接下去进行下一样车轮于。

统计 2     

经过总结:

先拿数组分隔成子数组,统计出子数组内部的逆序对的数额,然后再度统计出片只相邻子数组之间的逆序对的数据。

参考代码:

public class InversePairs {
    private int count = 0;

    public int InversePairs(int[] a) {
        if (a == null || a.length == 0)
            return -1;
        mergeSort(a, 0, a.length - 1);
        return count;
    }

    public void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }

    public void merge(int[] a, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int t = right - left;//临时数组下标
        int l = mid;
        int r = right;
        while (l >= left && r >= mid + 1) {
            if (a[l] > a[r]) {
                count += (r - mid);
                tmp[t--] = a[l--];
                if (count >= 1000000007) {
                    count %= 1000000007;
                }
            } else {
                tmp[t--] = a[r--];
            }
        }
        while (l >= left) {
            tmp[t--] = a[l--];
        }
        while (r >= mid + 1) {
            tmp[t--] = a[r--];
        }
        for (int i = 0; i <= right - left; i++) {
            a[left + i] = tmp[i];
        }
    }

    @Test
    public void testSolution() {
        int[] a = { 364, 637, 341, 406, 747, 995, 234, 971, 571, 219, 993, 407,
                416, 366, 315, 301, 601, 650, 418, 355, 460, 505, 360, 965,
                516, 648, 727, 667, 465, 849, 455, 181, 486, 149, 588, 233,
                144, 174, 557, 67, 746, 550, 474, 162, 268, 142, 463, 221, 882,
                576, 604, 739, 288, 569, 256, 936, 275, 401, 497, 82, 935, 983,
                583, 523, 697, 478, 147, 795, 380, 973, 958, 115, 773, 870,
                259, 655, 446, 863, 735, 784, 3, 671, 433, 630, 425, 930, 64,
                266, 235, 187, 284, 665, 874, 80, 45, 848, 38, 811, 267, 575 };
        System.out.println(InversePairs(a));//2519
    }
}