洛谷题单-贪心

牛奶

在这里插入图片描述在这里插入图片描述
传送门

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
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P1208
struct node
{
    int p; //价格
    int t; //拥有的数量
} man[100000];
bool cmp(node a, node b)
{
    return a.p < b.p;
}
int main()
{
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> man[i].p >> man[i].t;
    }
    sort(man + 1, man + 1 + m, cmp);
    long long ans = 0;
    int cnt = 0;
    while (n)
    {
        if (n > man[++cnt].t)
        {
            ans += man[cnt].p * man[cnt].t;
            n -= man[cnt].t;
        }
        else
        {
            ans += man[cnt].p * n;
            n = 0;
        }
    }
    cout << ans;
    return 0;
}

跳跳！

在这里插入图片描述

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
#include <bits/stdc++.h>
using namespace std;
// 贪心(在剩下的石头里找最大和最小来回跳)
// https://www.luogu.com.cn/problem/P4995#submit
int stone[100000];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> stone[i];
    }
    sort(stone + 1, stone + 1 + n);
    int rnode = n;
    int lnode = 0; // lnode 初值为1！因为一开始在地面
    bool flag = true;
    long long ans = 0;
    while (lnode != rnode)
    {
        if (flag)
        {
            ans += (stone[rnode] - stone[lnode]) * (stone[rnode] - stone[lnode]);
            lnode++;
            flag = false;
        }
        else
        {
            ans += (stone[rnode] - stone[lnode]) * (stone[rnode] - stone[lnode]);
            rnode--;
            flag = true;
        }
    }
    cout << ans;
    return 0;
}

纪念品分组

在这里插入图片描述

传送门

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
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P1094
int gift[100000];
int main()
{
    int m, n, cnt;
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> gift[i];
    }
    sort(gift + 1, gift + 1 + n);
    int rnode = n;
    int lnode = 1;
    cnt = 0;
    while (lnode < rnode)
    {
        if (gift[lnode] + gift[rnode] <= m)
        {
            cnt++;
            lnode++, rnode--;
        }
        else
        {
            rnode--;
            cnt++;
        }
    }
    if (lnode == rnode)
    {
        cnt++;
    }
    cout << cnt;
    return 0;
}

三国游戏

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
传送门

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
#include <bits/stdc++.h>
using namespace std;
int gen[10000][10000];
// 贪心+博弈论
// 每次选择第二大即可！
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            cin >> gen[i][j];
            gen[j][i] = gen[i][j];
        }
    }
    int ans = -1;
    for (int i = 1; i <= n; i++)
    {
        sort(gen[i] + 1, gen[i] + 1 + n, greater<int>());
        ans = max(ans, gen[i][2]);
    }
    cout << 1 << endl;
    cout << ans << endl;
    return 0;
}

推销员

在这里插入图片描述
在这里插入图片描述
传送门

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
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P2672
int N;
struct node
{
    int dis;
    int tire;
} a[100000];
int t[100000];    // t[i]代表前i个最大疲劳值前缀和
int d[100000];    // q[i]代表前i个最大疲劳值的用户中在距离花费的疲劳值
int post[100000]; // post[i]代表挑去i个最大疲劳值用户之后，剩下之中的最大值
bool cmp(node a, node b)
{
    return a.tire > b.tire;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i].dis;
    }
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i].tire;
    }
    sort(a + 1, a + 1 + N, cmp);
    for (int i = 1; i <= N; i++)
    {
        t[i] = t[i - 1] + a[i].tire;
    }
    for (int i = 1; i <= N; i++)
    {
        d[i] = max(d[i - 1], a[i].dis * 2);
    }
    for (int i = N; i >= 1; i--)
    {
        post[i] = max(post[i + 1], 2 * a[i].dis + a[i].tire);
    }
    for (int i = 1; i <= N; i++)
    {
        cout << max(t[i] + d[i], t[i - 1] + post[i]) << endl;
    }
    return 0;
}