贪心算法专题：最大子段和与纪念品分组详解

贪心算法专题：最大子段和与纪念品分组详解 | 极客日志

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];
int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    LL sum = 0;
    LL ret = -1e20;
    for(int i = 1; i <= n; i++){
        sum += a[i];
        ret = max(ret, sum);
        if(sum < 0) sum = 0;
    }
    cout << ret << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e4 + 10;
int a[N];
int main(){
    int n, w; cin >> w >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int l = 1, r = n;
    int ret = 0;
    while(l <= r) // 相遇时给物品还未分配
    {
        if(a[l] + a[r] <= w){ l++; r--; }
        else { r--; }
        ret++;
    }
    cout << ret << endl;
    return 0;
}

贪心算法专题：最大子段和与纪念品分组详解

一、贪心

1.1 什么是贪心算法

1.2 贪心算法的特点

1.3 如何学习贪心？

二、简单贪心的经典算法题

2.1 最大子段和

2.1.1 题目

2.1.2 算法原理

2.1.3 代码

2.1.4 贪心策略证明

2.1.4.1 证明过程：

2.2 纪念品分组

2.2.1 题目

2.2.2 算法原理

2.2.3 代码

2.2.4 贪心策略证明

2.2.4.1 证明过程：

更多推荐文章

相关免费在线工具

贪心算法专题：最大子段和与纪念品分组详解

一、贪心

1.1 什么是贪心算法

1.2 贪心算法的特点

1.3 如何学习贪心？

二、简单贪心的经典算法题

2.1 最大子段和

2.1.1 题目

2.1.2 算法原理

2.1.3 代码

2.1.4 贪心策略证明

2.1.4.1 证明过程：

2.2 纪念品分组

2.2.1 题目

2.2.2 算法原理

2.2.3 代码

2.2.4 贪心策略证明

2.2.4.1 证明过程：

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具