股票买卖

题目

原题链接

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式
第一行包含整数 N，表示数组长度。

第二行包含 N 个不大于 10000 的正整数，表示完整的数组。

输出格式
输出一个整数，表示最大利润。

数据范围
1 ≤ N ≤ 105

输入样例1：

1
2
6
7 1 5 3 6 4

输出样例1：

1
7

输入样例2：

1
2
5
1 2 3 4 5

输出样例2：

1
4

输入样例3：

1
2
5
7 6 4 3 1

输出样例3：

1
0

样例解释
样例1：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例2：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 0。

分析

这是一道很经典的贪心题，从实际含义出发考虑，如果要得到最大利润，我们可假设一种决策，只要有涨就卖。那么这种决策能否得到最优解呢？我们根据题目的限制可以发现，每个很大跨度的股票买卖都可以拆成若干个相邻跨度的股票买卖，那么如果我们在相邻的股票买卖做到有涨就卖，那么必然可以实现从第一天到最后一天的最大利润。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N];
int main()
{
    cin >> n;
    LL res = 0;
    for(int i = 0;i < n;i++) cin >> a[i];
    for(int i = 0;i + 1 < n;i++)
    {
        int d = a[i + 1]  - a[i];
        if(d > 0) res += d;
    }
    cout << res << endl;
    return 0;
}

货仓选址

题目

原题链接

在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式
第一行输入整数 N。

第二行 N 个整数 A1∼AN。

输出格式
输出一个整数，表示距离之和的最小值。

数据范围
1 ≤ N ≤ 100000,
0 ≤ Ai ≤ 40000

输入样例：

1
2
4
6 2 9 1

输出样例：

1
12

分析

这题乍一看，直觉上可能认为放在中间应该是最优的。实际上确实如此，那么我们如何证明放中间能使距离之和最小呢？，我们将题意转化为数学公式即可。

</div>
由此证明，我们不难写出以下代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N];
int main()
{
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];
    //排序
    sort(a,a + n);
    //选址位置为中位数
    int c = a[n / 2];
    LL res = 0;
    for(int i = 0;i < n;i++) res += abs(a[i] - c);
    cout << res << endl;
    return 0;
}

糖果传递

题目

原题链接

有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 1。

求使所有人获得均等糖果的最小代价。

输入格式
第一行输入一个正整数 n，表示小朋友的个数。

接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。

输出格式
输出一个整数，表示最小代价。

数据范围
1 ≤ n ≤ 1000000,
0 ≤ a[i] ≤ 2×10^9,
数据保证一定有解。

输入样例：

1
2
3
4
5
4
1
2
5
4

输出样例：

1
4

分析

这道题如果直接想的话很难下手，从公式出发会比较好理解一些。为此我们先把题意抽象成公式。

</div>
从公式出发，我们发现可以转化成上一题的思路进行求解。
为此，我们不难得出以下代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
//c[i]表示每行方程中的整体常数
int a[N],c[N];
int main()
{
    cin >> n;
    LL sum = 0;
    for(int i = 1;i <= n;i++) cin >> a[i],sum += a[i];
    //c[i - 1] = c[i] + avg - a[i - 1] 
    LL avg = sum / n;
    //递推求c数组
    c[1] = 0;
    for(int i = 2;i <= n;i++) c[i] = c[i - 1] - avg + a[i - 1];
    //对c数组执行一遍上题的逻辑
    sort(c + 1,c + 1 + n);
    LL res = 0,mid = c[(n + 1) / 2];
    for(int i = 1;i <= n;i++) res += abs(c[i] - mid);
    cout << res << endl;
    return 0;
}

雷达设备

题目

原题链接

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上，且雷达的监测范围为 d，当小岛与某雷达的距离不超过 d 时，该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系，定义海岸线为 x 轴，海的一侧在 x 轴上方，陆地一侧在 x 轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式
第一行输入两个整数 n 和 d，分别代表小岛数目和雷达检测范围。

接下来 n 行，每行输入两个整数，分别代表小岛的 x，y 轴坐标。

同一行数据之间用空格隔开。

输出格式
输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 −1。

数据范围
1 ≤ n ≤ 1000,
−1000 ≤ x,y ≤ 1000

输入样例：

1
2
3
4
3 2
1 2
-3 1
2 1

输出样例：

1
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
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
struct Seg
{
    double l,r;
    //根据区间右端点排序
    bool operator<(const Seg & s) const
    {
        return r < s.r;
    }
}segs[N];
int n,d;
int main()
{
    cin >> n >> d;
    for(int i = 0;i < n;i++)
    {
        int x,y;
        cin >> x >> y;
        if(y > d)
        {
            //没有解决方案
            cout << "-1" << endl;
            return 0;
        }
        double dif = sqrt(d * d - y * y);
        segs[i] = {x - dif,x + dif};
    }
    //对右端点排序
    sort(segs,segs + n);
    int res = 0;
    double last = -1e18;
    for(int i = 0;i < n;i++)
    {
        //当前区间最右边已经不能覆盖之后的区间了
        if(last < segs[i].l)
        {
            //增加一个雷达
            res++;
            //扩展当前区间
            last = segs[i].r;
        }
    }
    cout << res << endl;
    return 0;
}