分类目录归档：二分

CSP 201912-2 回收站选址

发表评论
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
#include <iostream>
#include <algorithm>

using namespace std;

struct coord {
    long long x, y;
    coord(){}
    coord(long long x, long long y) :x(x), y(y) {}
    bool operator == (const coord& coord2) const {
        return x == coord2.x && y == coord2.y;
    }
    bool operator < (const coord& coord2) const {
        if (x != coord2.x)return x < coord2.x;
        return y < coord2.y;
    }
}arr[10005];
int n;
int XArr[] = {0,0,1,-1,1,1,-1,-1};
int YArr[] = {1,-1,0,0,1,-1,1,-1};
int stat[5];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i].x >> arr[i].y;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        int cnter = 0;
        for (int j = 0; j < 4; j++) {
            coord tmp(arr[i].x + XArr[j], arr[i].y + YArr[j]);
            if (*lower_bound(arr, arr + n, tmp) == tmp)
                cnter++;
        }
        if (cnter != 4)continue;
        cnter = 0;
        for (int j = 4; j < 8; j++) {
            coord tmp(arr[i].x + XArr[j], arr[i].y + YArr[j]);
            if (*lower_bound(arr, arr + n, tmp) == tmp)
                cnter++;
        }
        stat[cnter]++;
    }
    for (int i = 0; i < 5; i++) {
        cout << stat[i] << "\n";
    }
}

lower_bound/upper_bound简易实现

发表评论

lower_bound:

1
2
3
4
5
6
7
8
9
int lower_bound(int v) { //arr[1..n],arr[0..n-1]
    int l = 0, r = n-1,mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (arr[mid]<v)l=mid+1;
        else r = mid;
    }
    return l;
}

upper_bound:

1
2
3
4
5
6
7
8
9
int upper_bound(int v) { //arr[1..n],arr[0..n-1]
    int l = 0, r = n-1,mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (arr[mid]<=v)l=mid+1;
        else r = mid;
    }
    return l;
}

洛谷10月月赛R2·浴谷八连测R3 -Chtholly- Chtholly Nota Seniorious

发表评论

洛谷题号：3933
乱搞、二分答案+贪心，根本想不出来，打暴力30分……

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
73
74
75
76
77
78
79
80
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
int n, m;
int arr[2005][2005];
int arr_rotate[2005][2005];
int pos[2005];
int minnum = 2e9, maxnum = 0;
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] >minnum+value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (maxnum - value > arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
/*check问题搞不懂可以仔细阅读T2题解
check的等效写法：
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] < maxnum - value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (minnum + value < arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
*/
void rotate90degrees(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            arr_rotate[j][n-i+1] = arr[i][j];
        }
    }
    memcpy(arr, arr_rotate, sizeof(arr));
    swap(n, m);
}

int solve(){
    int low = 0, high = maxnum - minnum,mid;
    while (low < high){
        mid = (low + high) / 2;
        if (check(mid)){
            high= mid;
        }
        else{
            low = mid + 1;
        }
    }
    return low;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
            maxnum = max(maxnum,arr[i][j]);
            minnum = min(minnum,arr[i][j]);
        }
    }
    int re = 2e9;
    for (int i = 1; i <= 4; i++){
        re = min(re, solve());
        rotate90degrees();
    }
    cout << re;
    return 0;
}

数据结构 邓俊辉 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 继续阅读 →

Openjudge 派 题解

发表评论

派
总时间限制: 1000ms 内存限制: 65536kB
描述
我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。
我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。
请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。
输入
第一行包含两个正整数N和F，1 ≤ N, F ≤ 10 000，表示派的数量和朋友的数量。
第二行包含N个1到10000之间的整数，表示每个派的半径。
输出
输出每个人能得到的最大的派的体积，精确到小数点后三位。
样例输入

3 3
4 3 3

样例输出

25.133

继续阅读 →

Openjudge 月度开销 题解

发表评论

月度开销
总时间限制: 1000ms 内存限制: 65536kB
描述
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。
约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。
约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。
输入
第一行包含两个整数N,M，用单个空格隔开。
接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。
输出
一个整数，即最大月度开销的最小值。
样例输入

7 5
100
400
300
100
500
101
400

样例输出

500

提示
若约翰将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大月度开销为500。其他任何分配方案都会比这个值更大。
继续阅读 →

Openjudge 河中跳房子 题解

发表评论

河中跳房子
总时间限制: 1000ms 内存限制: 65536kB
描述
每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。
在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。
农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。
请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？
输入
第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。
接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。
输出
一个整数，最长可能的最短跳跃距离。
样例输入

25 5 2
2
11
14
17
21

样例输出

4

提示
在移除位于2和14的两个岩石之后，最短跳跃距离为4（从17到21或从21到25）。
继续阅读 →

Openjudge Aggressive cows 题解

发表评论

Aggressive cows

总时间限制: 1000ms 内存限制: 65536kB
描述
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don’t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
输入
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Line i+1 contains an integer stall location, xi
输出
* Line 1: One integer: the largest minimum distance
样例输入

5 3
1
2
8
4
9

样例输出

3

提示
OUTPUT DETAILS:
FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.
Huge input data,scanf is recommended.
来源
USACO 2005 February Gold
继续阅读 →