蓝桥杯跟解(贪心)

1055. 股票买卖

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤N≤1051≤N≤105

输入样例1：

6
7 1 5 3 6 4

输出样例1：

7

简单的贪心

cpp版本

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

using namespace std;
const int N = 100010;

int n;
int arr[N];
int main(){
    cin >> n;
    for (int i = 0 ; i < n ; i ++){
        scanf("%d",arr + i);
    }
    int start = 0;
    int res = 0;
    for (int i = 1 ; i < n ; i ++){
        if (arr[i] < arr[start]) start = i;
        else{
            res += arr[i] - arr[start];
            start = i;
        }
    }
    cout << res <<endl;
}

python版本

#股票买卖II
#所有一段时间的交易都可以拆成过程量为1的交易的和
n = int(input())
arr = [int(i) for i in input().split()]

res = 0
for i in range(1,n):
    if arr[i] > arr[i - 1]:
        res += arr[i] - arr[i - 1]

print(res)

104. 货仓选址

在一条数轴上有 NN 家商店，它们的坐标分别为 A1A1~ANAN。

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

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

输入格式

第一行输入整数N。

第二行N个整数A1A1~ANAN。

输出格式

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

数据范围

1≤N≤1000001≤N≤100000

输入样例：

4
6 2 9 1

输出样例：

12

简单的贪心

cpp版本

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int arr[100010];

int main(){
    cin >> n;
    for(int i = 0 ; i < n ; i ++){
        scanf("%d",arr+i);
    }
    sort(arr,arr+n);

    long long res = 0;
    int i = 0;
    while (i < n - 1 - i){
        res += (long long)arr[n - i - 1] - arr[i];
        i += 1;
    }
    cout << res << endl;
}

pyhton版本

#货仓选址
n = int(input())
arr = [int(i) for i in input().split()]
arr.sort()
res = 0
i = 0
while i < n - 1 - i:
    res += arr[n - i - 1] - arr[i]
    i += 1

print(res)

122. 糖果传递

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例：

4
1
2
5
4

输出样例：

4

复杂的数列问题

cpp版本

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
int n;
const int N = 1000010;
int arr[N];
int C[N];
int main(){
    cin >> n;
    LL sum = 0;
    for(int i =0 ; i < n ; i ++){
        scanf("%d",arr + i);
        sum += (LL)arr[i];
    }
    LL ave = sum / n;

    for(int i =1 ; i < n ; i ++){
        C[i] = C[i - 1] - ave + arr[i - 1];
    }
    sort(C,C+n);
    int i = 0;
    LL res = 0;
    while (i < n - 1 - i){
        res += (LL)C[n - i - 1] - C[i];
        i += 1;
    }
    cout << res << endl;


    return 0;
}

python版本

#糖果传递(数学)
n = int(input())
arr = []
C = [0]*n
total = 0
for i in range(n):
    arr.append(int(input()))
    total += arr[i]
ave = total // n

for i in range(1,n):
    C[i] = C[i - 1] - ave + arr[i - 1]
C.sort()


res = 0

i = 0
while i < n - i - 1:
    res += C[n - i - 1] - C[i]
    i += 1

print(res)

112. 雷达设备

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

1≤n≤10001≤n≤1000

输入样例：

3 2
1 2
-3 1
2 1

输出样例：

2

区间贪心

cpp版本

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1010;

struct node{
    double left,right;
}S[N];

int n;
double R;

bool cmp(node a,node b){
    return a.right < b.right;
}

int main(){
    cin >> n >> R;

    for (int i = 0 ;i < n ; i ++){
        double x,y;
        scanf("%lf %lf",&x,&y);
        if(abs(y) > R) {
            cout << -1 << endl;
            return 0;
        }
        S[i].left = x - sqrt(R*R - y*y);
        S[i].right = x + sqrt(R*R - y*y);
    }
    sort(S,S+n,cmp); 


    int res = 1;
    double start = S[0].right;
    for(int i =1 ; i < n ;i ++){
        if (S[i].left <= start) continue;
        else{
            start = S[i].right;
            res += 1;
        }
    }
    cout << res << endl;

}

python版本

n,R = map(int,input().split())
flag = False
data = []
for i in range(n):
    a,b = map(int,input().split())
    temp = pow(R*R - b*b,0.5)
    if b > R:
        print(-1)
        flag = True
        break
    data.append((a - temp,a + temp))

data = sorted(data,key = lambda x : x[1])  #按照右端点排序

if flag == False:
    res = 1
    start = data[0][1]

    for i in range(1,n):
        if data[i][0] <= start:
            continue
        else:
            start = data[i][1]
            res += 1

    print(res)

1235. 付账问题

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

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

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

其中第 ii 个人带了 aiai 元。

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

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤5×1051≤n≤5×105,
0≤ai,S≤1090≤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

分配剩余价格问题

cpp版本

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int n;
double S;
const int N = 500010;
int arr[N];
double out[N];
double ave;
bool flag = false;
double S_square(double *out){
    double res;
    for(int i = 0 ; i < n ; i ++){
        //cout << out[i] << ' ';
        res += (out[i] - ave)*(out[i] - ave);
    }
    //cout << endl;
    res = sqrt(res / n);
    return res;
}


int main(int argc, char** argv) {
    cin >> n >> S;
    for(int i = 0; i < n ; i ++){
        scanf("%d",arr + i);
    }
    sort(arr,arr+n);

    ave = (double)S / n;
    double newAve = ave;
    double curLeft = 0.0;
    double fen = 0.0;
    int start = 0;

    while (1){
        //cout << 1 << endl;
        for(int i = start; i < n ; i ++){
            if(arr[i] <= newAve) {
                out[i] = arr[i];
                curLeft += newAve - arr[i];
            }
            else{

                if(i == start){
                    //cout << 1 << endl;
                    flag = true;
                    for(int j = start ; j < n ;j ++){
                        out[j] = newAve;
                    }
                    flag = true;
                }
                else{
                    start = i;
                }
                break;

            }
        }

        if (flag) break;
        if (start == n - 1){
            out[n - 1] = ave + curLeft;
            break;
        }


        fen = curLeft / (n - start);
        newAve += fen;
        //cout << newAve << "Ave" << curLeft << "curLeft" <<n - start<< endl;
        curLeft = 0.0;

    }

    //cout << ave << endl;
    //for(int i = 0 ; i< n ; i ++){
    //  cout << arr[i] << ' ';
    //}
    //cout << endl;
    //cout << S_square(out) << endl;
    printf("%.4lf\n",S_square(out));
    return 0;
}

python版本

#付账问题
n,s = map(int,input().split())
arr = [int(i) for i in input().split()]
out = [0]*(n+1)

arr.sort()
ave = s / n
curAve = ave

start = 0
curLeft = 0
flag = False #停止条件
while True:
    for i in range(start,n):
        if arr[i] <= curAve:
            curLeft += curAve - arr[i]
            out[i] = arr[i]
        else:
            if start == i:
                for i in range(start,n):
                    out[i] = curAve
                    flag = True
                break

            else:
                start = i
                break

    if flag:
        break

    curAve += curLeft / (n - start)
    curLeft = 0


res = 0
for i in range(n):
    res += pow(out[i] - ave,2)

res /= n
print("%.4f"%pow(res,0.5))

1239. 乘积最大

给定 NN 个整数 A1,A2,…ANA1,A2,…AN。

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

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

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

输入格式

第一行包含两个整数 NN 和 KK。

以下 NN 行每行一个整数 AiAi。

输出格式

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

数据范围

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

输入样例1：

5 3
-100000
-10000
2
100000
10000

输出样例1：

999100009

输入样例2：

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

输出样例2：

-999999829

双指针

cpp版本

#include <iostream>
#include <algorithm>

using namespace std;


typedef long long LL;
const int N = 100010,mod = 1000000009;
int n,k;
int arr[N];
int res = 1;
int main(){
    cin >> n >> k;
    for(int i = 0 ; i < n ; i ++){
        scanf("%d",arr + i);
    }
    sort(arr,arr+n);
    int sign = 1;
    int left = 0,right = n - 1;
    if(k % 2== 1){
        res = arr[right];
        right -= 1;
        k -= 1;
        if (res < 0) sign = -1;
    }
    while (k){
        LL x = (LL)arr[left]*arr[left + 1],y = (LL)arr[right]*arr[right - 1];
        if (x * sign > y * sign){
            res = x % mod * res % mod;
            left += 2;
            k -= 2;
        }
        else{
            res = y % mod * res % mod;
            right -= 2;
            k -= 2;
        }
    }
    cout << res << endl;
}

python版本

#乘积最大(双指针)
def mod(a,b,M):
    if a * b < 0:
        return -((-a * b) % M)
    else:
        return a * b % M


M = 1000000009
n,k = map(int,input().split())
arr = []
for i in range(n):
    arr.append(int(input()))
arr.sort()


left = 0
right = n - 1
sign = 1

res = 1
if k % 2 == 1:
    res = arr[right]
    right -= 1
    k -= 1
    if res < 0:
        sign = -1

while k:
    x = arr[left]*arr[left + 1]
    y = arr[right]*arr[right - 1]
    if x*sign > y*sign:
        res = mod(res,x,M)
        left += 2
        k -= 2
    else:
        res = mod(res,y,M)
        right -= 2
        k -= 2

print(res)

1247. 后缀表达式

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

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

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

输入格式

第一行包含两个整数 NN 和 MM。

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

输出格式

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

数据范围

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

输入样例：

1 1
1 2 3

输出样例：

4

逆波兰表达式(负号的选择)

cpp版本

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
int n,m;
const int N = 200010;
int arr[N];
int main(){
    cin >> n >> m;
    int maxSam = -99999999;
    int minSam = 99999999;
    int maxIndex,minIndex;
    for(int i = 0 ; i < n+m+1; i ++){
        scanf("%d",arr + i);
        if (maxSam < arr[i]){
            maxIndex = i;
            maxSam = arr[i];
        }
        if (minSam > arr[i]){
            minIndex = i;
            minSam = arr[i];
        }
    }

    LL res = 0;

    if (m > 0){
        res = -1*(LL)minSam + (LL)maxSam;
        for(int i = 0 ; i < n+m+1 ; i ++){
            if(i == maxIndex || i == minIndex) continue;
            if (arr[i] < 0) res -= (LL)arr[i];
            else res += (LL)arr[i];
        }
    }
    else{
        for(int i = 0 ; i < n + m + 1 ; i ++){
            res += (LL)arr[i];
        }
    }
    cout << res << endl;
}

python版本

#后缀表达式
n,m = map(int,input().split())
arr = [int(i) for i in input().split()]

res = 0

if m == 0:
    print(sum(arr))
else:
    maxSam = -float('inf')
    minSam = float('inf')
    for var in arr:
        minSam = min(minSam,var)
        maxSam = max(maxSam,var)
        if var < 0:
            res -= var
        else:
            res += var

    if minSam > 0:
        res -= 2*minSam
    if maxSam < 0:
        res += 2*maxSam

    print(res)

1248. 灵能传输

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

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

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

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

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

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

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

输入格式

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

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

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

接下来一行包含 nn 个数 a1,a2,⋅⋅⋅,ana1,a2,···,an。

输出格式

输出 TT 行。

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

数据范围

1≤T≤3,3≤n≤300000,|ai|≤1091≤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

样例解释

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

前缀和的交换，排序的平滑交换

cpp版本

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

using namespace std;

const int N = 300010;
typedef long long LL;
int T;
LL res[N],preSum[N];
bool vis[N];

int main(){
    cin >> T;
    while(T --){
        memset(preSum,0,sizeof preSum);
        memset(res,0,sizeof res);
        memset(vis,false,sizeof vis);

        int n;
        scanf("%d",&n);

        for(int i = 1 ;i <= n ; i ++){
            scanf("%lld",preSum + i);
            preSum[i] += preSum[i - 1];
        }

        LL p0 = preSum[0],pn = preSum[n];
        if (p0 > pn) swap(p0 , pn);

        sort(preSum,preSum+n+1);

        //定位p0与pn的位置
        for(int i = 0 ; i <= n ; i ++){
            if (preSum[i] == p0 ){
                p0 = i;
                break;
            }
        }

        for(int i = n ; i >= 0 ; i --){
            if (preSum[i] == pn ){
                pn = i;
                break;
            }
        }

        int l = 0;
        int r = n;
        for(int i = p0 ; i >= 0 ; i -= 2){
            res[l ++] = preSum[i];
            vis[i] = true;
        }
        for(int i = pn ; i <= n ; i += 2){
            res[r --] = preSum[i];
            vis[i] = true;
        }
        for(int i = 0 ; i <= n ; i ++){
            if (vis[i] == false){
                res[l ++] = preSum[i];
            }
        }
        LL ans = -9999999999;
        for(int i = 1 ; i <= n ; i ++){
            ans = max(ans,abs(res[i] - res[i - 1]));
        }
        cout << ans << endl;
    }
    return 0;
}

python版本

#灵能传输
t = int(input())
for i in range(t):

    n = int(input())
    arr = [int(i) for i in input().split()]
    preSum = [0]
    for i in range(n):
        preSum.append(preSum[i]+arr[i])


    p0 = preSum[0]
    pn = preSum[n]
    if p0 > pn:
        p0,pn = pn,p0

    preSum.sort()
    for i in range(n+1):
        if p0 == preSum[i]:
            p0 = i
            break
    for i in range(n,-1,-1):
        if pn == preSum[i]:
            pn = i
            break

    vis = [False]*(n+1)
    res = [0]*(n+1)
    ans = -float('inf')

    left = 0
    right = n
    for i in range(p0,-1,-2):
        res[left] = preSum[i]
        left += 1
        vis[i] = True
    for i in range(pn,n+1,2):
        res[right] = preSum[i]
        right -= 1
        vis[i] = True
    for i in range(n+1):
        if vis[i] == False:
            res[left] = preSum[i]
            left += 1
    for i in range(1,n+1):
        ans = max(abs(res[i] - res[i - 1]),ans)

    print(ans)