首页 > 代码库 > Problem E: 穷游中国在统题 优先队列 + 模拟

Problem E: 穷游中国在统题 优先队列 + 模拟

http://www.gdutcode.sinaapp.com/problem.php?cid=1049&pid=4

 

Problem E: 穷游中国在统题

Description

Travel_poorly队是广工大目前最年轻的金牌队伍,队内成员分别是tmk、YFQ、Maple。这天他们接到教练的order要给新生杯统题,统题是个不轻松的工作,要评估各个题目的难度,设计出一套有梯度的套题,使得做题的情况有区分度。tmk很快想出了解决的办法,他给每道题目都设置了一个难度值,然后按照难度值进行筛选题目,这时候他发现难度值刚开始有可能是无序的,于是他决定要让全部题目都按照难度值从小到大排好序。 这时候YFQ说让他来排序,排序是一个展现算法魅力的过程,他要通过一种有趣的方法来给题目的难度值排序: 首先他把题目划分成很多组,每组的题目都是连续的,例如某一组包含从i到j的题目,那么这一组包含的是第i,i+1,i+2,i+3,...,j题。 这样每道题都属于某一个组,然后他再到组内把题目按照难度值进行从小到大排序。 当每个组内都进行排序之后,最终全部题目的难度值将按照从小到大的顺序排列好。 我们知道每一组里面的题目越多,排序的压力就越大,所以Maple提出一个合理的要求,就是让每个组里面的题目数量尽可能的少,聪明的ACMer,你知道Travel_poorly一共要分出多少个组吗?

Input

第一行是一个整数t ( t<= 10 ),表示有t组数据。在每组数据中: 第一行是一个整数n ( n<=1000 00 ),表示题目的总数; 第二行是n个整数A1,A2,A3...An ( 0<=Ai<= 1000 000 000),表示每道题目的难度值

Output

对于每组数据,输出一个正整数,表示一共要分出多少个组能满足Travel_poorly的要求,每两组样例之间输出一个空行。

Sample Input

2 5 3 2 5 4 6 5 5 4 3 2 1

Sample Output

3 1

HINT

 
[Submit][Status][Web Board]

考虑下这个列子吧

2 4 1 3 5

2 4 1 5 3

 

首先它的数字不是1--n的,而且可能重复。

那么就离散化吧。把他们离散到1--n中。注意,如果数字是2、1、5、4、2

那么离散后的结果是2、1、5、4、3,总是要把她们离散到1---n

至于怎么离散,如果离散成2、1、5、4、2很容易,就是排序 + lowerbound

那么用book[val]表示这个数字出现了多少次,加上权值就可以了。

至于为什么我要离散成这样。就是因为其实这题每次都是要把最小的数字归位。

比如样例1,一开始我肯定是要让最小的那个数字,就是1,归位的吧,所以区间数字的数量最小都是3.

然后归位的时候发现途中有一个4,所以区间数字的数量要更改为4.(如果a[4]是5,那么就要变成5)

然后就在剩下的数字中,(现在只身下5)去找一个最小的数字归位。

其实就是模拟题,只不过每次必须的任务是把最小的数字归位。

离散成这样的目的是相对大小很明显,知道需要比较到那一位数字。

复杂度是O(nlogn)的

 

技术分享
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 100000 + 20;
int b[maxn];
int a[maxn];
int book[maxn];
bool vis[maxn];
struct node {
    int val, pos;
    bool operator < (const struct node & rhs) const {
        if (val != rhs.val) return val > rhs.val;
        else return pos > rhs.pos;
    }
};
priority_queue<struct node>que;
void work() {
    while (!que.empty()) que.pop();
    memset(book, 0, sizeof book);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
        a[i] = b[i];
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
        book[a[i]]++;
        a[i] += book[a[i]] - 1;
    }
//    for (int i = 1; i <= n; ++i) {
//        printf("%d ", a[i]);
//    }
//    printf("\n");
    memset(vis, false, sizeof vis);
    for (int i = 1; i <= n; ++i) {
        struct node t;
        t.pos = i;
        t.val = a[i];
        que.push(t);
        assert(vis[a[i]] == false);
        vis[a[i]] = true;
    }
    int ans = 0;
    int lef = -inf;
    int be = 1;
    while (!que.empty()) {
        struct node t = que.top();
        que.pop();
        if (t.pos <= lef) continue;
        lef = t.pos;
        int mx = -inf;
        while (true) {
            int tmx = mx;
            for (int i = be; i <= lef; ++i) {
                mx = max(a[i], mx);
            }
            if (tmx == mx) {
                be = mx + 1;
                lef = mx;
                break;
            }
            be = lef + 1;
            lef = mx;
        }
        ans++;
    }
    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    int t;
    scanf("%d", &t);
    while (t--) {
        work();
        if (t) printf("\n");
    }
    return 0;
}
View Code

 

Problem E: 穷游中国在统题 优先队列 + 模拟