算法学习——贪心

1.股票买卖II

题目

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

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

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

输入格式

第一行包含整数 N，表示数组长度。

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

输出格式

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

数据范围

1≤N≤105

输入样例1：

6
7 1 5 3 6 4

输出样例1：

7

输入样例2：

5
1 2 3 4 5

输出样例2：

4

输入样例3：

5
7 6 4 3 1

输出样例3：

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.输入N
2.输入N个数            数组中的第 i 个数字表示一个给定股票在第 i 天的价格。
3.输出最大利润
*/

#include<iostream>
using namespace std;
const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];
    
    int res = 0;
    for(int i = 0;i + 1 < n;i++)
    {
        int dt = a[i + 1] - a[i];
        if(dt > 0) res += dt; 
    }
    cout << res << endl;
    return 0;
}

2.货舱选址

题目

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

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

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

输入格式

第一行输入整数N。

第二行N个整数A1~AN。

输出格式

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

数据范围

1≤N≤100000

输入样例：

4
6 2 9 1

输出样例：

12

分析

贪心

代码

/*
1.输入N
2.N个整数A1~AN




3.输出距离最小值之和

*/

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

int a[N];
int n;

int main()
{
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];
    
    sort(a,a + n);
    int c = a[n / 2];
    
    int res = 0;
    for(int i = 0;i < n;i++) res += abs(a[i] - c);
    
    cout << res << endl;
    return 0;
}

3. 糖果传递

题目

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤1000000
数据保证一定有解。

输入样例：

4
1
2
5
4

输出样例：

4

分析

罗列出式子
找规律
最后得出每一个x都可以用x1表示出来


把ci 全解出来
排序
找出中间点
和上道题一样

注意：
在计算的过程中，有一个数是LL，则其他的所有的数也得是LL，要不然会出错

代码

/*
1.输入n
2.输入n行数字  a[i]
3.输出最小代价

*/
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 1000010;
int n;
int a[N];
LL c[N];  //存放c数组的

int main()
{
    LL sum = 0;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    
    LL ave = sum / n;
    
    //求出c数组
    c[1] = 0;
    for(int i = n;i > 1;i--)
        c[i] = c[i + 1] + ave - a[i];
    
    //排序
    sort(c + 1,c + n + 1);
    
    //求结果
    LL res = 0;
    for(int i = 1;i <= n;i++)   
        res += abs(c[i] - c[(n + 1) / 2]);
    cout << res << endl;
    return 0;
}

4. 雷达设备

题目

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

1≤n≤1000

输入样例：

3 2
1 2
-3 1
2 1

输出样例：

2

分析

逆向思维

从小岛出发

而不是从雷达出发

贪心策略

代码

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

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

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


2.贪心



3.输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出“-1”。
*/


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>

using namespace std;

const int N = 1010;
int n,d;  

struct Segment
{
    double l,r;
    bool operator< (const Segment& t) const
    {
        return r < t.r;
    }
    
}seg[N];

int main()
{
    cin >> n >> d;
    bool faild = false;  //失败的真假
    
    for(int i = 0;i  < n;i++)
    {
        int x,y;
        cin >> x >> y;
        if(y > d) faild = true;  //直接找不到了
        else
        {
            //标出线段
            double len = sqrt(d * d - y * y);
            seg[i].l = x - len,seg[i].r = x + len;
        }
    }
    
    if(faild) printf("-1");
    else
    {
        //排序
        sort(seg,seg + n);
        
        double last = -1e20;
        int cnt = 0;

        //遍历右端点
        for(int i = 0;i < n;i++)
        {
            if(last  < seg[i].l)  //不包括的情况
            {
                cnt++;
                last = seg[i].r;
            }
        }
        printf("%d",cnt);
    }
    return 0;
    
}

5.付账问题

题目

几个人一起出去吃饭是常有的事。

但在结帐的时候，常常会出现一些争执。

现在有 n 个人出去吃饭，他们总共消费了 S 元。

其中第 i 个人带了 ai 元。

幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。

这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。

你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。

形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :

p1.png

输入格式

第一行包含两个整数 n、S；

第二行包含 n 个非负整数 a1, …, an。

输出格式

输出最小的标准差，四舍五入保留 4 位小数。

数据范围

1≤n≤5×105,
0≤ai,S≤109

输入样例1：

5 2333
666 666 666 666 666

输出样例1：

0.0000

输入样例2：

10 30
2 1 4 7 4 8 3 6 4 7

输出样例2：

0.7928

分析

贪心

代码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;

const int N = 500010;

int n;  //人数
int a[N];

int main()
{
    double s;  //总钱数
    cin >> n >> s;
    for(int i = 0;i <n;i++) cin >> a[i];
    
    sort(a,a + n);
    double res = 0,ave = s / n;
    
    for(int i = 0;i < n;i++)
    {
        double cur = s / (n - i);  //注意这里的均值是在不断变化的，为了使得其他的尽可能平分
        if(a[i] < cur) cur = a[i];  //不够
        res += (ave - cur) * (ave - cur);
        s -= cur;
    }
    printf("%.4lf",sqrt(res / n));
    return 0;
    
    
    
    
    
    return 0;
}

6. 乘积最大

题目

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

输出格式

输出一个整数，表示答案。

数据范围

1≤K≤N≤105,
−105≤Ai≤105

输入样例1：

5 3
-100000
-10000
2
100000
10000

输出样例1：

999100009

输入样例2：

5 3
-100000
-100000
-2
-100000
-100000

输出样例2：

-999999829

分析

贪心
分类讨论

实际上就是左边选一串，右边选一串，然后做比较，选大的那一个。

代码

/*
输入：
第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

*/

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 100010,mod = 1000000009;

int n,k;
int a[N];

int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n;i++) scanf("%d",&a[i]);
    
    sort(a,a + n);
    
    int l = 0,r = n - 1;
    int sign = 1;  //正负号
    int res = 1;
    
    
    //如果是奇数，转化为偶数  先选掉最大的那一个
    if(k % 2)
    {
        res = a[r--];
        k--;
        if(res < 0) sign = -1;  //特判所有的数都为负数的情况
    }
    
    while(k)
    {
        LL x = (LL)a[l] * a[l + 1],y = (LL)a[r - 1] * a[r];
        if(x * sign > y * sign)
        {
            res = x % mod * res % mod;
            l += 2;
        }
        else
        {
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }
    cout << res << endl;
    return 0;
}

7. 后缀表达式

题目

给定 N 个加号、M 个减号以及 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1，小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用 123+−，则 “23+1−” 这个后缀表达式结果是 4，是最大的。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1。

输出格式

输出一个整数，代表答案。

数据范围

0≤N,M≤105,
−109≤Ai≤109

输入样例：

1 1
1 2 3

输出样例：

4

分析

1 ~ M + N 个符负号 ，都可以构造出来

代码

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 200010;

int a[N];
int n,m,k;

int main()
{
    cin >> n >> m;  //n个加号  m个减号
    k = m + n + 1;
    for(int i = 0;i < k;i++) cin >> a[i];
    
    sort(a,a + k);
    
    LL res = 0;
    //全是正数的情况
    if(!m) 
    {
        for(int i = 0;i < k;i++) res += a[i];
    }
    
    else
    {
        //第一个必须是正数，加上最大的，减去最小的（最小的是负数的情况：max  最小的是正数的情况：max）
        res = a[k - 1] - a[0];
        for(int i = 1;i < k - 1;i++) res += abs(a[i]);
    }
    cout << res << endl;
    return 0;
}

8. 灵能传输

题目

在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对一片区域内的敌军造成毁灭性的伤害。

经常用于对抗人类的生化部队和虫族的刺蛇飞龙等低血量单位。

你控制着 n 名高阶圣堂武士，方便起见标为 1,2,⋅⋅⋅,n。

每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少（ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态）。

现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i∈[2,n−1]，若 ai≥0 则其两旁的高阶圣堂武士，也就是 i−1、i+1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能；若 ai<0 则其两旁的高阶圣堂武士，也就是 i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。

形式化来讲就是 ai−1+=ai,ai+1+=ai,ai−=2ai。

灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为 maxni=1|ai|，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。

输入格式

本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。

接下来依次输入每一组询问。

每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。

接下来一行包含 n 个数 a1,a2,⋅⋅⋅,an。

输出格式

输出 T 行。

每行一个整数依次表示每组询问的答案。

数据范围

1≤T≤3,3≤n≤300000,|ai|≤109,

每个评测用例的限制如下：。

输入样例1：

3
3
5 -2 3
4
0 0 0 0
3
1 2 3

输出样例1：

3
0
3

输入样例2：

3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1

输出样例2：

5
7
4

样例解释

样例一
对于第一组询问：
对 2 号高阶圣堂武士进行传输操作后 a1=3，a2=2，a3=1。答案为 3。
对于第二组询问：
这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。

分析

一个跳跃性的想法：
前缀和
一个惊人的性质：
交换了

又因为：

所以此题的目的就是让 前缀和两两之间的差值尽可能小
所以说 ：排序就可以了

两种情况：

第一种：s0 sn 可以动（题中不是这种情况）

第一种：s0 sn 不可以动（题中是这种情况）

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;
typedef long long LL;

const int N = 300010;

int n;
LL a[N],s[N];
bool st[N];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        s[0] = 0;
        for(int i = 1;i <= n;i++) 
        {
            scanf("%lld",&a[i]);
            s[i] = s[i - 1] + a[i];
        }
        
        //找出s[0] 和 s[n] 的位置
        LL s0 = s[0],sn = s[n];
        if(s0 > sn) swap(s0,sn);
        sort(s,s + n + 1);
        for(int i = 0;i <= n;i++)
        {
            if(s[i] == s0)
            {
                s0 = i;
                break;
            }
        }
        for(int i = n;i >= 0;i--)
        {
            if(s[i] == sn)
            {
                sn = i;
                break;
            }
            
        }
        
        memset(st,0,sizeof st);
        int l = 0,r = n;
        for(int i = s0;i >= 0;i -= 2)   //隔一个走一个
        {
            a[l++] = s[i];
            st[i] = true;
        }
        for(int i = sn;i <= n;i += 2)
        {
            a[r--] = s[i];
            st[i] = true;
        }
        
        //剩下的没走过的
        for(int i = 0;i <= n;i++)
        {
            if(!st[i])
            {
                a[l++] = s[i];
            }
        }
        
        LL res = 0;
        for(int i = 1;i <= n;i++) 
        {
            res = max(res,abs(a[i] - a[i - 1]));
        }
        printf("%lld\n",res);
    }
    return 0;
}

本文地址：https://blog.csdn.net/ironman321/article/details/108070768