分类目录归档：排序

CSP 202012-2 期末预测之最佳阈值

1条回复

这题也不知道咋回事，我想了个异想天开的做法，也不知道行不行，交上去竟然过了！哈哈哈哈哈哈。
暴力的N^2做法可以得70，我写个异想天开的排序+前缀和做法100。
感觉有必要写个题解，在这里写一下。

本题的大致意思是，给出一堆人的学习努力程度（用一个非负整数表示）和其是否挂科（并不必然成正相关，其中可能混杂学习努力程度高的人也挂科的情况）。要求找到一个学习努力程度基准分数，使得用该基准评判学生的努力程度时，判断对的最多。

我主要利用差分的思想进行解题。对于一个分数，我们其实只需要知道通过与挂科的人数的差值即可。基准分数是否应该低于或高于某一特定学习努力程度分数，在于其能否为总人数作出贡献。例如，如果一个分数有3人通过，3人挂科，则不管选择比他低的基准还是比他高的基准，则都对总的人数做出了3的贡献，可以相互抵消。但若4人通过，3人挂科，则更应该优先选择比其低的基准，因为这样的话，判断对的就多了一个。

首先建立一个map对输入的数据进行排序。由于选择指标的时候只看努力程度不看人，因此可以将同努力程度的人们聚合起来。如果该人挂科，在是否通过的数组cnt里-1，如果通过则+1.这样就产生了一个差分的数组cnt。此时，该数组cnt表示的是在选定该分数作为基准后，通过的人比挂科的人多多少。

然后，对其进行前缀和操作。借助前缀和，我们可以得到数组presum，可以计算选择任意基准分数时，通过的人比挂科的人多多少。还可计算选择任意基准分数时，挂科的人比通过的人多多少（通过对计算值取负）。这样，我们分别计算高于基准分数通过的人比挂科的人多多少，和低于基准分数时挂科的人比通过的人多多少。将他们相加，就可以得到一个判断正确的人数的差分。统计这些差分的最大值，就可以算出对应的基准分数。

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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>

using namespace std;

int m;
map<int, int> stat;
int arrSize = 0;
int y[100005], cnt[100005], presum[100005];

int main() {
    ios::sync_with_stdio(false);
    cin >> m;
    while (m--) {
        int y, result;
        cin >> y >> result;
        stat[y] += result ? 1 : -1;
    }
    for (auto iter = stat.begin(); iter != stat.end(); iter++) {
        int ind = iter->first, v = iter->second;
        y[arrSize] = ind;
        cnt[arrSize] = v;
        arrSize++;
    }
    presum[0]=cnt[0];
    for(int i=1;i<arrSize;i++){
        presum[i]=presum[i-1]+cnt[i];
    }
    int index=0, cmpValue=presum[arrSize-1];
    for(int i=1;i<arrSize;i++){
        int tmpV=presum[arrSize-1]-presum[i-1]*2;
        if(tmpV>=cmpValue){
            cmpValue=tmpV;
            index=i;
        }
    }
    cout<<y[index];
}

洛谷 逆序对

发表评论

题号：1908

讲道理，这个是我之前在洛谷上做的，今天突然看到逆序对这个问题，感觉很重要，然后就回洛谷翻评测记录把逆序对这道题找出来把代码贴到博客上。

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,arr[40005],arr_temp[40005];
int cnt;
void MergeSort(int start,int end){//[start,end]
    if(start==end)return;
    MergeSort(start,(start+end)/2);
    MergeSort((start+end)/2+1,end);
    memcpy(arr_temp+start,arr+start,sizeof(int)*(end-start+1));
    int ptr1=start,ptr2=(start+end)/2+1,ptr_main=start;
    while(ptr1<=(start+end)/2&&ptr2<=end){
        if(arr_temp[ptr1]<arr_temp[ptr2]){
            arr[ptr_main]=arr_temp[ptr1];
            ptr1++;
        }else{
            arr[ptr_main]=arr_temp[ptr2];
            ptr2++;
            cnt+=(start+end)/2-ptr1+1;
        }
        ptr_main++;
    }
    for(;ptr1<=(start+end)/2;ptr1++){
        arr[ptr_main]=arr_temp[ptr1];
        ptr_main++;
    }
    for(;ptr2<=end;ptr2++){
        arr[ptr_main]=arr_temp[ptr2];
        ptr_main++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr[i];
    MergeSort(1,n);
    cout<<cnt;
}

20180730更新：又写了一遍，再贴代码：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
int n;
int arr[40005];
int tmparr[40005], tmparr2[40005];
int rop = 0;
void mergeSort(int l, int r) {
    if (l == r)return;
    int ls = l, le = (l + r) / 2, rs = (l + r) / 2 + 1, re = r;
    mergeSort(ls, le);
    mergeSort(rs, re);
    int lp = ls, rp = rs, cp = l;
    while (lp <= le && rp <= re) {
        if (tmparr[lp] < tmparr[rp])tmparr2[cp++] = tmparr[lp++];
        else {
            tmparr2[cp++] = tmparr[rp++];
            rop += le - lp +1;
        }
    }
    for (; lp <= le; lp++)tmparr2[cp++] = tmparr[lp];
    for (; rp <= re; rp++)tmparr2[cp++] = tmparr[rp];
    memcpy(tmparr + l, tmparr2 + l, sizeof(int)*(r - l + 1));
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    memcpy(tmparr, arr, sizeof(arr));
    mergeSort(1, n);
    cout << rop;
}

20200409更新：题目更新了，数据加强了。做了小小改动。

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
#include<iostream>
#include<cstring>
using namespace std;
long long n;
long long arr[500005];
long long tmparr[500005], tmparr2[500005];
long long rop = 0;
void mergeSort(long long l, long long r) {
    if (l == r)return;
    long long ls = l, le = (l + r) / 2, rs = (l + r) / 2 + 1, re = r;
    mergeSort(ls, le);
    mergeSort(rs, re);
    long long lp = ls, rp = rs, cp = l;
    while (lp <= le && rp <= re) {
        if (tmparr[lp] <= tmparr[rp])tmparr2[cp++] = tmparr[lp++];
        else {
            tmparr2[cp++] = tmparr[rp++];
            rop += le - lp + 1;
        }
    }
    for (; lp <= le; lp++)tmparr2[cp++] = tmparr[lp];
    for (; rp <= re; rp++)tmparr2[cp++] = tmparr[rp];
    memcpy(tmparr + l, tmparr2 + l, sizeof(long long) * (r - l + 1));
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (long long i = 1; i <= n; i++)cin >> arr[i];
    memcpy(tmparr, arr, sizeof(arr));
    mergeSort(1, n);
    cout << rop;
}

数据结构 邓俊辉 PA#1 灯塔(LightHouse) 题解

发表评论

灯塔(LightHouse)

Description

As shown in the following figure, If another lighthouse is in gray area, they can beacon each other.

For example, in following figure, (B, R) is a pair of lighthouse which can beacon each other, while (B, G), (R, G) are NOT.

Input

1st line: N

2nd ~ (N + 1)th line: each line is X Y, means a lighthouse is on the point (X, Y).

Output

How many pairs of lighthourses can beacon each other

( For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same )

Example

Input

3
2 2
4 3
5 1

Output

1

Restrictions

For 90% test cases: 1 <= n <= 3 * 105

For 95% test cases: 1 <= n <= 106

For all test cases: 1 <= n <= 4 * 106

For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same.

1 <= x, y <= 10^8

Time: 2 sec

Memory: 256 MB

Hints

The range of int is usually [-231, 231 – 1], it may be too small.

描述

海上有许多灯塔，为过路船只照明。

（图一）

如图一所示，每个灯塔都配有一盏探照灯，照亮其东北、西南两个对顶的直角区域。探照灯的功率之大，足以覆盖任何距离。灯塔本身是如此之小，可以假定它们不会彼此遮挡。

（图二）

若灯塔A、B均在对方的照亮范围内，则称它们能够照亮彼此。比如在图二的实例中，蓝、红灯塔可照亮彼此，蓝、绿灯塔则不是，红、绿灯塔也不是。

现在，对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。

输入

共n+1行。

第1行为1个整数n，表示灯塔的总数。

第2到n+1行每行包含2个整数x, y，分别表示各灯塔的横、纵坐标。

输出

1个整数，表示可照亮彼此的灯塔对的数量。

样例

见英文题面

限制

对于90%的测例：1 ≤ n ≤ 3×105

对于95%的测例：1 ≤ n ≤ 106

全部测例：1 ≤ n ≤ 4×106

灯塔的坐标x, y是整数，且不同灯塔的x, y坐标均互异

1 ≤ x, y ≤ 10^8

时间：2 sec

内存：256 MB

提示

注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为[-231, 231 – 1]，不一定足够容纳本题的输出。

继续阅读 →

数据结构 邓俊辉 PA#1 范围查询(Range) 题解

发表评论

范围查询(Range)
Description
Let S be a set of n integral points on the x-axis. For each given interval [a, b], you are asked to count the points lying inside.

Input
The first line contains two integers: n (size of S) and m (the number of queries).

The second line enumerates all the n points in S.

Each of the following m lines consists of two integers a and b and defines an query interval [a, b].

Output
The number of points in S lying inside each of the m query intervals.

Example
Input

5 2
1 3 7 9 11
4 6
7 12
Output

0
3
Restrictions
0 <= n, m <= 5 * 10^5 For each query interval [a, b], it is guaranteed that a <= b. Points in S are distinct from each other. Coordinates of each point as well as the query interval boundaries a and b are non-negative integers not greater than 10^7. Time: 2 sec Memory: 256 MB 描述 数轴上有n个点，对于任一闭区间 [a, b]，试计算落在其内的点数。 输入 第一行包括两个整数：点的总数n，查询的次数m。 第二行包含n个数，为各个点的坐标。 以下m行，各包含两个整数：查询区间的左、右边界a和b。 输出 对每次查询，输出落在闭区间[a, b]内点的个数。 样例 见英文题面 限制 0 ≤ n, m ≤ 5×105 对于每次查询的区间[a, b]，都有a ≤ b 各点的坐标互异 各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数 时间：2 sec 内存：256 MB 继续阅读 →