huring
0%

51node-2502-分块

Posted on In

题目：
小b有个长度为n的数组a，她想将这个数组排序。

然而小b很懒，她觉得对整个数组排序太累了，因此她请你将a分成一些块，使得她只需要对每一块分别排序，就能将整个数组排序。

请问你最多能把a分成多少块。

保证a为0…n-1的一个排列。

样例解释：

将a分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] ，排序得到的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

输入
第一行一个数n；
第二行n个数表示a[i]，以空格隔开。
n<=10
输出
输出一个数表示划分块的数量
输入样例
5
4 3 2 1 0
输出样例
1
解法：每个数字排序前排序后的下标为一段线段，相交的线段何为一段，最后求出剩下线段的个数即可。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<set>
#include<algorithm>
using namespace std;
int a[10];
struct point
{
    int num;
    int index;
    int sor;
};
bool cmp(point a, point b)
{
    return a.num < b.num;
}
point p[10];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d",&p[i].num);
        p[i].index = i;
    }
    sort(p, p + n, cmp);
    for(int i = 0; i < n; i++)
        p[i].sor = i;
    for(int i = 1; i < n ;i++){
        for(int j = i - 1;j >= 0; j--){
           // printf("i:%d %d %d   j: %d %d %d\n",i,p[i].index,p[i].sor,j,p[j].index,p[j].sor);
            int il = min(p[i].index, p[i].sor);
            int ir = max(p[i].index, p[i].sor);
            int jl = min(p[j].index, p[j].sor);
            int jr = max(p[j].index, p[j].sor);
            bool flag = false;
            if(il == jl || ir == jr)
                flag =  true;
            if(il < jl && ir > jl)
                flag = true;
            if(jl < il && jr > il)
                flag = true;
            int Min = min(min(p[i].index,p[j].index), min(p[i].sor,p[j].sor));
            int Max = max(max(p[i].index,p[j].index), max(p[i].sor,p[j].sor));
            if(flag)
            {
                for(int k = 0; k < i; k++){
                    if(p[i].index == p[k].index && p[i].sor == p[k].sor){
                        p[k].index = Min;
                        p[k].sor = Max;
                    }
                }
                p[i].index = Min;
                p[i].sor = Max;
                for(int k = 0; k < j; k++){
                    if(p[j].index == p[k].index && p[j].sor == p[k].sor){
                        p[k].index = Min;
                        p[k].sor = Max;
                    }
                }
                p[j].index = Min;
                p[j].sor = Max;
                
            }
            
        }
    }
    set<int> s;
   // for(int i = 0; i < n; i++)
        //printf("%d %d %d\n",i,p[i].index,p[i].sor);
    for(int i = 0; i < n; i++)
        s.insert(p[i].index);
    printf("%d\n", s.size());
}