Part1.1 基础算法-贪心算法

A 活动安排

法一：我们按照左端点来进行排序

将区间按照区间左端点进行从小到达排序，然后，我们来进行分析
我们贪心的来考虑，ans(答案)、ed(前一个区间的右区间)
我们用最贪心的角度来考虑，为了让1到n容纳更多的区间，我们找到两种也只有这两种可以让结果更有的方法
1.如果当前区间的右端点小于ed，那么，ed=右端点
2.如果当前区间的左端点大于ed，那么，ed=左端点，ans++；
代码如下

/**@author SunLakeWalk*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")using namespace std;#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y secondtypedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;const int N = 1010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);int n;
priority_queue<PII, vector<PII>, greater<PII>> q;void work()
{
    ios;cin >> n;for (int i = 0; i < n; i ++ ){
    int x, y; cin >> x >> y;y --;q.push({
    x, y});}int ans = 0, st = 0, ed = 0;while (q.size()){
    PII t = q.top();q.pop();if (ed < t.x){
    ans ++;ed = t.y;// cout << t.x << ' ' << t.y << endl;}if (ed > t.y){
    ed = t.y;}}cout << ans << endl;
}int main()
{
    //ios;int T = 1;// cin >> T;while (T -- ){
    work();}return 0;
}

法二：我们按照区间右端点进行排序 （比法一更好）

当按照区间右端点进行排序的时候，我们可以只看当前的区间左端点是否大于前面的ed，
因为，我们是按照的区间右端点进行排序的，所以，所有的区间只有两种情况，
第一种，相交，第二不相交
如果相交，还不如取前面的那一个，所以，我们可以不管，不用处理
如果不相交，那恰恰就是我们想要的，可以开展的新的一个活动

/**@author SunLakeWalk*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <vector>
#include <queue>using namespace std;struct Node
{
    int x, y;bool operator> (const Node &W) const{
    return y > W.y;}
};int n;
priority_queue<Node, vector<Node>, greater<Node>> q;void work()
{
    cin >> n;for (int i = 0; i < n; i ++ ){
    int x, y; cin >> x >> y;y --;q.push({
    x, y});}int ans = 0, ed = 0;while (q.size()){
    Node t = q.top();q.pop();if (ed < t.x){
    ans ++;ed = t.y;}}cout << ans << endl;
}int main()
{
    //ios;int T = 1;// cin >> T;while (T -- ){
    work();}return 0;
}

B 种树

原本是想用区间左端点来排序，但是发现写起来好复杂呀，考虑的情况有些多。
设前一个区间是pre
要考虑：
1.pre.y >= t.y
2.pre.y>=t.y&& pre.y < t.y
3.pre.y < t.x
所以，我们还是用区间右端点来进行排序吧。
对每个区间进行一次处理
先将这个区间扫描一下，记一下已经统计的个数
然后，如果不够的话，从后往前扫描，在没种树的地方种下树。
下面是代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;struct Node
{
    int x, y, z;
};int n, h;
Node q[N];
bool vis[N];
int ans;bool cmp(Node a, Node b)
{
    return a.y < b.y;
}int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> h;for (int i = 0; i < h; i ++ ){
    int x, y, z; cin >> x >> y >> z;q[i] = {
    x, y , z};}sort(q, q + h, cmp);Node pre = {
    0, 0, 0};for (int i = 0; i < h; i ++ ){
    Node t = q[i];int cnt = 0;for (int j = t.x; j <= t.y; j ++ ){
    if (vis[j]) cnt ++;}if (cnt < t.z){
    for (int j = t.y; j >= t.x; j -- ){
    if (!vis[j]){
    vis[j] = true;cnt ++;ans ++;}if (cnt == t.z) break;}}}cout << ans << endl;return 0;
}

C喷水装置

以区间左端点升序排序，然后，每次在有重合的区间中找到右区间延展最长的那个区间，并记录个数

下面是代码

#include <bits/stdc++.h>using namespace std;const int N = 20010;struct Node
{
    double x, y;bool operator< (const Node &W) const{
    return x < W.x;}
}q[N];int n, l, w;
int cnt;void read()
{
    cin >> n >> l >> w;cnt = 0;for (int i = 0; i < n; i ++ ){
    double x, r; cin >> x >> r;if (r * 2 <= w) continue;double d = sqrt(r * r - w * w / 4.0);q[cnt].x = x - d;q[cnt].y = x + d;cnt ++;}
}void solve()
{
    int ans = 0, i = 0, sign = 0;double ed = 0;while (ed < l){
    ans ++;double s = ed;//固定前面选好的区间的右端点for (; q[i].x <= s && i <= cnt; i ++ ){
    //找到一个可以延伸最长的区间if (ed < q[i].y)ed = q[i].y;}//如果没法延伸下去，同时还没有到达尾端，则失败了if (ed == s && s < l){
    cout << -1 << endl;return;}}cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T; cin >> T;while (T -- ){
    read();sort(q, q + cnt);solve();}return 0;
}

D加工生产调度

johnson算法：
1.Mi = min(ai, bi)
2.升序排序
3.若Mi = a[i],从头开始放
若Mi = b[i]，从尾开始放

#include <bits/stdc++.h>using namespace std;const int N = 1010;struct Node
{
    int x, id;bool operator< (const Node &W) const{
    return x < W.x;}
}m[N];int n;
int a[N], b[N];
int ans[N], sum;int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;for (int i = 0; i < n; i ++ ) cin >> a[i];for (int i = 0; i < n; i ++ ) cin >> b[i];for (int i = 0; i < n; i ++ ){
    m[i] = {
    min(a[i], b[i]), i};}sort(m, m + n);int st = 0, ed = n - 1;for (int i = 0; i < n; i ++ ){
    // cout << m[i].id << ' ';if (m[i].x == a[m[i].id]) ans[st ++] = m[i].id;else ans[ed -- ] = m[i].id;}cout << endl;int t = 0;for (int i = 0; i < n; i ++ ){
    t += a[ans[i]];if (sum < t) sum = t;sum += b[ans[i]];}cout << sum << endl;for (int i = 0; i < n; i ++ ) cout << ans[i] + 1 << ' ';cout << endl;return 0;
}

E智力大冲浪

每个任务都有完成的最后期限，都有对应的罚款大小
贪心的来考虑。
要是罚款最少，我们要尽可能的先完成罚款较大的任务，而且要将这个任务放在期限的最左侧，以减少占用其他任务的完成。
我们将任务降序排序，然后，从当前的期限，向前遍历，如果为排满，就放上它，如果排满了，说明它过期了，要被罚，将他从从后一个位置开始照个空位放上去。
算法证明：
如果次算法不是最优的，说明有一个过期的任务k，可以安排进日期内。
如果，我们要将他放进合法日期内，就必须将其中一个任务拿出来，但是，因为我们是按照任务的罚款降序排序，所以合法日期
内的所有数字都不小于当前日期的罚款，那我们这么操作，不会产生更优的结果，所以，算法得证。

#include <bits/stdc++.h>using namespace std;const int N = 1010;int n, m;
struct Node
{
    int t, w;bool operator< (const Node &W) const{
    return w > W.w;}
}q[N];bool vis[N];
int ans = 0;int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> m >> n;for (int i = 1; i <= n; i ++ ) cin >> q[i].t;for (int i = 1; i <= n; i ++ ) cin >> q[i].w;sort(q + 1, q + 1 + n);// for (int i = 1; i <= n; i ++ ) cout << q[i].w << ' ';// cout << endl;for (int i = 1; i <= n; i ++ ){
    bool has_find = false;for (int j = q[i].t; j >= 1; j -- ){
    if (!vis[j]){
    has_find = true;vis[j] = true;break;}}if (!has_find){
    int j;for (j = n; j >= 1; j -- ){
    if (!vis[j]){
    vis[j] = true;break;}}ans += q[i].w;}}cout << m - ans << endl;return 0;
}

E智力大冲浪

很常规的贪心问题。

#include <bits/stdc++.h>using namespace std;const int N = 1010;int n, m;
struct Node
{
    int t, w;bool operator< (const Node &W) const{
    return w > W.w;}
}q[N];bool vis[N];
int ans = 0;int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> m >> n;for (int i = 1; i <= n; i ++ ) cin >> q[i].t;for (int i = 1; i <= n; i ++ ) cin >> q[i].w;sort(q + 1, q + 1 + n);// for (int i = 1; i <= n; i ++ ) cout << q[i].w << ' ';// cout << endl;for (int i = 1; i <= n; i ++ ){
    bool has_find = false;for (int j = q[i].t; j >= 1; j -- ){
    if (!vis[j]){
    has_find = true;vis[j] = true;break;}}if (!has_find){
    int j;for (j = n; j >= 1; j -- ){
    if (!vis[j]){
    vis[j] = true;break;}}ans += q[i].w;}}cout << m - ans << endl;return 0;
}

F 数列极差

很常规的贪心

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <cctype>
#include <numeric>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")using namespace std;#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y secondtypedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;const int N = 100010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);int n;
priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int> > q2;void work()
{
    int x;cin >> n;while (n -- ){
    cin >> x;q1.push(x);q2.push(x);}int t = q1.top();q1.pop();while (q1.size()){
    t = t * q1.top() + 1;q1.pop();}// cout << t << "\n";// cout << q1.top() << "\n";while (q2.size() > 1){
    x = q2.top();q2.pop();int y = q2.top();q2.pop();q2.push(x * y + 1);}// cout << q2.top() << "\n";// cout << q2.size() << "\n";cout << q2.top() - t << "\n";
}int main()
{
    //ios;int T = 1;// cin >> T;while (T -- ){
    work();}return 0;
}

G 数列分段

很常规的贪心

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <cctype>
#include <numeric>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")using namespace std;#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y secondtypedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;const int N = 100010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);int cnt, sum;
int n, m;
int a[N];void work()
{
    scanf("%d%d", &n, &m);cnt = 1;for (int i = 0; i < n; i ++ ){
    int x; scanf("%d", &x);if (sum + x > m){
    cnt ++;sum = x;}else{
    sum += x;}}printf("%d\n", cnt);
}int main()
{
    //ios;int T = 1;// cin >> T;while (T -- ){
    work();}return 0;
}

H 线段

很常规的贪心思想

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <cctype>
#include <numeric>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")using namespace std;#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y secondtypedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;const int N = 1000010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);int n;
struct Node
{
    int x, y;bool operator< (const Node &W) const{
    return y < W.y;}
}a[N];void work()
{
    scanf("%d", &n);for (int i = 1; i <= n; i ++ ){
    int x, y; scanf("%d%d", &x, &y);a[i] = {
    x, y};}sort(a + 1, a + 1 + n);int cnt = 0;int ed = -1;for (int i = 1; i <= n; i ++ ){
    int x = a[i].x, y = a[i].y;// printf("%d %d %d\n", ed, x, y);if (ed <= x){
    cnt ++;ed = y;}else{
    continue;}}printf("%d\n", cnt);
}int main()
{
    //ios;int T = 1;// cin >> T;while (T -- ){
    work();}return 0;
}

F家庭作业

按照绩点从高到底排序，然后顺序选择结束时间，每次判断是否当前时间是否被用过，如果没有，就选当前的成绩，如果被用了，就去找当前时间前面的最高成绩
首先贪心的来考虑，按照绩点从高到低来排序，然后，我们尽量将当前的作业放到结束之前尽可能靠后的位置**{在结束之前找一个空闲的位置，如果自己的位置空着，就放在当前，否则就放在靠自己最近的位置}**。因为，如果放到结束时间后就不会产生贡献，放在靠前的位置一定不如靠后的位置更优。假设当前完成时间为t，靠前位置为t-a，靠后位置为t-b，且a<b，对于完成时间t，能放在t-a，同时一定能放在位置t-b，同时，放在t-b的位置一定能比放在t-a占的完成时间在（t-a）前面的位置更少。所以，放的越靠后越贪心。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;struct Node
{
    int t, c;bool operator< (const Node &W) const{
    if (c == W.c) return t < W.t;return c > W.c;}
}a[N];int n;
int pre[N];//指向当天的前一天
bool st[N];int get(int x)
{
    if (!st[x]){
    //如果当前这一天没有被占用的话，//那就很好直接用当前这一天一定是最贪心的。// st[x] = true;return x;}else{
    //否则的话，就向前去找， 如果没有被用掉就可以使用这一天//这一定是最贪心的//假设最贪心的不是这一天t，而是这一天前面的某一天tt的话//后面的任务能放到tt前面的，一定被t前面的天包括。// int t = get(pre[x]);// pre[x] = t;// return t;return pre[x] = get(pre[x]);}
}
int main()
{
    scanf("%d", &n);for (int i = 1; i <= 700000; i ++ )pre[i] = i - 1;for (int i = 1; i <= n; i ++ ){
    scanf("%d%d", &a[i].t, &a[i].c);}sort(a + 1, a + 1 + n);int sum = 0;for (int i = 1; i <= n; i ++ ){
    int t = a[i].t;int k = get(t);if (!k) continue;st[k] = true;// printf("%d\n", k);if (k) sum += a[i].c;}printf("%d\n", sum);return 0;
}

J钓鱼

直接暴力啊。。。。

/* 题目说从第一个鱼塘往右走，在当前鱼塘停留若干时间后接着往下一个鱼塘走 直到时间被消耗完。 因为不好知道到底在那个地方停下，直觉上感觉这个题可以二分 二分最后停留的鱼塘的位置，100个鱼塘，最多二分七次就OK了 先给消耗的时间加上经过鱼塘消耗的时间好吧，不能二分。。。 不具备单调性哦然后，维护一个大根堆。 每次取出当前可钓的鱼的最大数量，然后将减少后的鱼量放进去 如果在时间还没有消耗完的情况下，出现了负数的情况就直接退出循环*/
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>using namespace std;typedef pair<int, int> PII;#define x first
#define y secondconst int N = 110;int n, m;
int a[N], t[N], s[N];
int ans;int work(int pos)
{
    int ans = 0;int sum = s[pos];//消耗pos个五分钟if (sum >= m) return -1;priority_queue<PII> q;for (int i = 1; i <= pos; i ++ )q.push({
    a[i], t[i]});// printf("%d\n", pos);// printf("%10d %d\n", sum, m);while (sum < m)//消耗时间要小于总时间{
    PII t = q.top();q.pop();// printf("%d %d\n", t.x, t.y);if (t.x < 0){
    break;}ans += t.x;q.push({
    t.x - t.y, t.y});sum ++;}// printf("%d\n", ans);return ans;
}// bool check(int mid)
// {
    
// int cnt = work(mid);
// // printf("%d\n", mid);
// puts("--------------------------");
// // printf("%10d %d\n", mid, cnt);
// if (cnt > ans)
// {
    
// ans = cnt;
// return true;
// }
// return false;
// }
int main()
{
    scanf("%d%d", &n, &m);m *= 12;for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ ) scanf("%d", &t[i]);for (int i = 2; i <= n; i ++ ){
    int x; scanf("%d", &x);s[i] = s[i - 1] + x;}// int l = 1, r = n;// while (l <= r)// {
    // int mid = l + r >> 1;// if (check(mid)) r = mid;// else l = mid + 1;// printf("%d %d %d\n", l, mid, r);// }for (int i = 1; i <= n; i ++ )ans = max(ans, work(i));printf("%d\n", ans);return 0;
}

K糖果传递

设x为前一个小朋有需要向后一个小朋友传递的糖果数，下面我们将题目进行转化

【我也搞不清要不要裂开，似乎是需要裂开的，这样才能像仓库选址，因为仓库选址本身就是在一条直线上的】在众多x中，因为他们自己的糖果数不同，所以他们相互传递的糖果数也不同，所以会出现x是正数、负数、和0.我们找到一个位置，这里的a的右边是负数，左边是正数或0。可以将这个点拆开，变成一条链。这个点表示，需要向左边分配0个或多个糖果，也也要向右边分配糖果。
再结合前面我们转化的关系， 这样我们会发现，我们要让|xn - S1|, |xn - S2|, |xn - s3|, ...., |xn - Sn|最小，这就是需要先排个序，然后在中间位置坐标的点选择建立仓库，然后计算最短距离之和。就变成了仓库选址模型了。