首页 > 代码库 > 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
考虑下这个列子吧
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; }
Problem E: 穷游中国在统题 优先队列 + 模拟
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。