二分,递归,分治!!!
题意
集训队内的氛围是相当和谐的,如果某个问题上双方产生了争执会通过智力或是武力来解决问题。
集训队内的每个人有各自的武力值和智力值,如果一个队员x的智力值和武力值均大于等于另一个队员y,则x与y的争执中x必定获胜(保证没有两个人武力值和智力值均相同)
队长想知道队内有多少队员能恰好在争执中击败一个其他队员,又有多少队员能恰好在争执中击败两个其他队员,又有多少队员能恰好在争执中击败三个其他队员。。。。
由于每个数都问一遍太麻烦了,你只需要对0-(N-1)的每一个数都输出一遍就好啦
输入
输入的第一行包括了集训队成员的数量N (1<=N<=15000),下面N行描述了每个队员的武力值a和智力值b(0<=a,b<=32000)。输入队员按智力值排序,智力值相同则按武力值排序
输出
输出包括N行,每行一个数字。第一行为能恰好在争执中击败0个其他队员的队员数量,第二行为能恰好在争执中击败1个其他队员的队员数量,以此类推,最后一行为能恰好在争执中击败N-1个其他队员的队员数量
分析
这题究竟让我们干什么?
就是给我们n个坐标,让我们找每一个坐标可以包含的坐标数,然后统计,最后输出正好包含0个坐标的有多少
正好包含1个坐标的有多少,正好包含2个坐标的有多少,,,,,,,,,
OK,这种题我们凭借直觉知道我们是肯定要按照x或y轴其中一个进行排序的。
假设我们对x轴排序这样我们就只需比较,y轴就行了。
现在,我们按照x轴从小到大排序,如果x相等,那么按照y轴从小到大排序。
这样,在不存在两个完全一样的坐标的情况下,我们从左向右遍历,遍历到a[i]
那么a[i]所能包含的坐标一定在i之前,也就是我们已经遍历过的坐标!!!!!!
那么自然而然,我们可以这样做:
创建一个容器b
我们从左向右遍历,被遍历一个都push到容器b中
在此之前,我们先找到容器b中y坐标小于等于我目前遍历到的坐标的wy坐标的数量
这个数量就是我能包含的坐标数!
其实,看看题目,出题人都已经包我们排好序了,我们读取进来其实只需对y坐标所在的数组进行处理了,x轴坐标所在的数组根本不用去管。
这个算法的时间复杂度是O(n^2)
显然我们是无法接受的,下面我们要优化。
很容易想到,利用二分查找进行优化,我们对容器b进行从小到大的有序维护
在拿到a[i]时,upper_bound一下减去开头,这样我们就可以得到b中小于a[i]的数有多少个了。
得到之后,再将a[i]插入
这是看似十分正确的做法。但却是错误的!!
因为,插入也是要耗时的。。。。。。。。。如果我们选择插入耗时时间为常数的容器list
那么二分的部分就无法实现了,虽然可以进行二分查找,但是却无法通过减去开头的迭代器从而得出小于等于
a[i]的值的数目。
真是糟糕!!!!
我们不得不在采用别的思路了!!!!!!(当时的我真的很失望)
偷偷看一下标题。。“分治,递归”
我们再看我们实际要解决的问题。
对于数组: [1,1,1,2,3,42,1,3,4,1,0,4,44,5,23,42,1,5,1,3,5,78,4,6,9,3]
我们要求对于a[i]他前面有几个小于等于他的数。
整体二分!!
假设我们得出了[0,mid]中每一个元素的答案,与[mid,n]中每一个元素的答案
那么[0,mid]其实就是在[0,n]这个区间中的正确答案。
而我们在对[0,mid]中的区间排个序,对于[mid,n]中的每一个元素,向[0,mid]中去二分搜索,是否就可行了呢?
可行!!!!
需要注意的有两点:
1.如果我们对区间[l,r]实行这个算法,那么所得到答案a[i]前小于等于a[i]的数目,也是在这个区间的数目,而不会是在[0,n]大区间的数目。但是,这点不用在意,因为最终我们将会在[0,n]进行这个算法,一直相加就好了。
2.再进行排序时,我们会打乱原来数组的顺序,我们应该复制一个相同的数组,在这个数组中进行排序。(光靠口说,很难体会,建议自己编码感受)
下面代码,注意细节
#include<iostream> #include<algorithm> using namespace std; const int max_n = 32100; int x[max_n]; int y[max_n]; int a[max_n]; int b[max_n]; int c[max_n]; int n; void solve(int l,int r) { if (r - l <= 1)return; int mid = (l + r) >> 1; solve(l, mid);solve(mid, r); sort(c + l, c + mid); for (int i = mid;i < r;i++) a[i] += upper_bound(c + l, c + mid, y[i]) - c - l; } int main() { ios::sync_with_stdio(0); cin >> n; for (int i = 0;i < n;i++) { cin >> y[i] >> x[i]; c[i] = y[i]; } solve(0,n); for (int i = 0;i < n;i++)b[a[i]]++; for (int i = 0;i < n;i++) cout << b[i] << endl; }