贪心

1953. 你可以工作的最大周数 - 力扣（LeetCode）

假设按顺序排列 C1，C2… Cn

那么Cn >= Cn - 1 则Cn - 1 必定可以插在Cn的空里面 那Cn - 2就一定可以插在Cn - 1的空里（也可以插在别的数的空里） 所以前面的数是一定可以插入的

关键就在最后一个数 如果前面所有数都去插他的空 还不够的话 那后面的就不能用了

所以分两种情况 前n - 1个数的sum > 最大数Cn则所有数都可以插入 答案为sum + Cn

否则 只有sum * 2 + 1个数可以（拿Cn去插 sum的空）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) 
    {
        long long m = *max_element(milestones.begin(), milestones.end());
        long long rest = accumulate(milestones.begin(), milestones.end(), 0LL) - m;
        if (m > rest + 1)
        return rest * 2 + 1;
        else return rest + m;
    }
};

104. 货仓选址 - AcWing题库

  • 3/5

尽量选在中间位置 比如1 2 6 9

选择在2 6 中间 距离和为 2x - 3 + 15 - 2x = 12

选在6 9中间为 9 - x - 9 + 3x 并且x > 6 sum > 12

所以在中间是最好的

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
#include <iostream>
#include <algorithm>
using namespace std;
int nums[100010];
int main()
{
    int n;
    cin>>n;
    for (int i = 0; i < n; i++)
    {
        cin>>nums[i];
    }
    
    sort(nums, nums + n);
    int left = 0, right = 0;
    for (int i = 0; i < n / 2; i++)
    {
        left += nums[i];
    }
    for (int i = n / 2 + n % 2; i < n; i++)
    {
        right += nums[i];
    }
    cout<<right - left<<endl;
}

0填充 - 蓝桥云课 (lanqiao.cn)

  • 3/6

贪心的策略 从0到n 一旦遇到了两两凑成一对的 就直接计入结果并且跳过i + 1

如果遇到？ 大概有这几种情况 0??1 0?可以 ?1 可以

??11 ??可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include<cstring>
using namespace std;
int main()
{
  // 请在此输入您的代码
  string s;
  cin>>s;
  long long ans = 0;
  for (int i = 0; i < s.size() - 1; i++)
  {
      if (s[i] == s[i + 1] || s[i] == '?' || s[i + 1] == '?')
      {
          ans++;
          i++;
      }
  }
  cout<<ans;
  return 0;
}

122. 糖果传递 - AcWing题库

  • 3/12

[环形]均分纸牌问题

image-20240302163447063

推公式：先设每个人要给左边的$x_i$个 从右边拿到$x_{i + 1}$个 （只需要给旁边的 因为就算跨着给 结果也是一样的 直接设只给旁边的好算） 

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N], temp[N], c[N];
int main()
{
    int n;
    cin>>n;
    ll sum = 0, ret = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    ll ave = sum / n;
    for (int i = 0; i < n; i++)
    {
        temp[i] = ave - a[i];
    }
    c[0] = temp[0];
    for (int i = 1; i < n; i++)
    {
        c[i] = c[i - 1] + temp[i];
    }
    sort(c, c + n);
    int xn = c[n / 2];
    for (int i = 0; i < n; i++)
    {
        ret += abs(c[i] - xn);
    }
    cout<<ret;
}

112. 雷达设备 - AcWing题库

  • 3/11

本来想这样贪心：先按x从小到大 相同x的y从大到小排序 不断选取最右边的值 但是有些情况不符合 image-20240302195003434

所以要先求出每个岛的探测区间 然后再按区间合并的方法来做

按右端点排序 排完序后如果一个区间的左端点小于last区间的右端点 那么就说明他们可以共用一个雷达

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef pair<double, double> PII;
#define r first
#define l second
PII seg[100010];
const double INF = 1e10, eps = 1e-6;
int main()
{
    int n, d;
    cin >> n >> d;

    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin>>x>>y;
        if (y > d)
        {
            cout << -1 << endl;
            return 0;
        }
        auto len = sqrt(d * d - y * y);
        seg[i] = {x + len, x - len};
    }
    
    sort(seg, seg + n);
    int res = 0;
    double last = -INF;
    for (int i = 0; i < n; i++)
    {
        if (seg[i].l > last + eps)
        {
            res++;
            last = seg[i].r;
        }
    }
    
    cout << res;
}

1235. 付账问题 - AcWing题库

求出平均值 当小于平均值的 时候 直接allin 当大于平均值的时候只需要给出平均值就行

关键在于不断地更新当前的平均值

一开始想的贪心是 先把小于的全部给了 大于的把平均值给了 然后算差的钱的平均值 再从大的里面减 然后不够了再去… 这样要两层循环 是$O(n^2)$的 不行

可以对每一个数都更新一下当前的平均值 小于的全部给 但是由于小于平均值 这里要更新一下当前的平均值 因为这人给的不够 后面要多给 由于排序了 如果有人够了 就直接给平均值的钱就行 因为后面的必然够

注意同时计算sum

注意这题爆double了（哭 要用long doubleimage-20240302205938546

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int nums[500010];
int main()
{
    int n;
    long long s;
    cin>>n>>s;
    long double ave = s * 1.0 / n ;
    for (int i = 0; i < n; i++)
    {
        cin>>nums[i];
    }
    long double cur_ave = ave;
    long double sum = 0;
    sort(nums, nums + n);
    for (int i = 0; i < n; i++)
    {
        if (nums[i] <= cur_ave)
        {
            s -= nums[i];
            sum += (ave - nums[i]) * (ave - nums[i]);
            cur_ave = s  * 1.0 / (n - i - 1);
        }
        else 
        {
            sum += (cur_ave - ave) * (cur_ave - ave);
        }
    }
    printf("%.4llf",sqrt(sum / n));
}

1239. 乘积最大 - AcWing题库

  • 3/7
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
48
49
50
51
52
53
54
55
56
57
58
/*
k是奇数则 如果全是负数 结果为负
否则先选一个正数（最大的） 变为k是偶数的情况
k是偶数则答案必然是正的 看负数的个数 
*/

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

typedef long long LL ;
const int N = 100010 , mod = 1000000009 ;
int a[N];

int main()
{
    int n , k ;
    scanf("%d%d",&n,&k);
    for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);

    sort(a,a + n);

    LL res = 1 ; //乘积初始化
    int l = 0 , r = n - 1 ;//双指针初始化
    int sign = 1 ; // 符号初始化

    //由于4种情况除了 k 是奇数且 k < n 的时候需要特判一下处理一下符号 ,其他的时候都可以转化为双指针做法
    //k 是奇数是先选出最大的数, k-- 就是偶数,两边再同时取对,转化成相同的双指针做法
    if(k % 2 )
    {
        res =  a[r]; // 取出最大的一个数
        r -- ; //右指针移动
        k -- ; //个数减1

        if(res < 0) sign = -1;  // 如果最大值都是负数,就证明全是负数,那么符号要发生改变
    }
    while(k) // 双指针做法
    {
        LL x = (LL)a[l] * a[l + 1] , y = (LL)a[r] * a[r - 1];//两边同时取对
        //选择更大的一对,和归并排序思路相近
        if(x * sign > y * sign)
        {
            res = x % mod * res % mod; // 需要注意的是 :不可以写成(x * res) % mod ,也不可以写成是 res % mod * x % mod
                                       // 因为x最大是 10^10，如果不先取模的话，和res相乘的结果最大是 10^19,会暴long long。            
            l += 2; // 指针移动                                 
        }
        else 
        {
            res = y % mod * res % mod; 
            r -= 2; 
        }
        k -= 2; 
    }
    printf("%lld",res);
    return 0;
}

1247. 后缀表达式 - AcWing题库

  • 3/12

一开始没读懂题意 后缀表达式关键在于他转换成中缀表达式 是可以随意添加括号的 所以说 根据负负得正的原则 我们可以将负数转化成正数 比如 -1 -2 -3 1 2 3 可以是1 +2+3-(-1-2-3)

贪心：先选最大的数作为基数 如果没有减号那就是全部相加 如果有一个减号 那就把所有负数变成正的 如果没有负的就要减去最小的正数 所以一开始直接减去最小的那个数 然后把1~n+m-1的数全部按绝对值加起来就可以

如果有多个减号 通过加括号 可以变成跟一个减号一样

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
#include <iostream>
#include <algorithm>
using namespace std;
int nums[300010];
int main()
{
    int n, m;
    cin>>n >> m;
    for (int i = 0; i < n + m + 1; i++)
    {
        cin>>nums[i];
    }
    
    sort(nums, nums + n + m + 1);
    
    long long res = nums[n + m];
    if (m == 0)
    {
        for(int i = 0; i < n + m; i++)
        {
            res += nums[i];
        }
    }
    else 
    {
        res -= nums[0];
        for (int i = 1; i < n + m; i++)
        {
            res += abs(nums[i]);
        }
    }
    
    cout<<res;
}

1248. 灵能传输 - AcWing题库

  • 3/4

太困难了 最后还是没看懂题解 但是学到了：

每次中间的给两边的能量 求最小的最大值 每次传输完能量后前缀和会由 s[i - 1] s[i] s[i + 1]变成s[i] s[i - 1] s[i + 1] 这就说明了所有的前缀和都可以任意排序 当顺序排序的时候差值最小 最大值就最小

algorithm
#algorithm
贪心
https://brtulien.github.io/2024/01/22/贪心/
作者
Brtulien
发布于
2024年1月22日
更新于
2024年7月1日
许可协议