【蓝桥杯专题】 贪心（C++ | 洛谷 | acwing | 蓝桥）_蓝桥杯 山谷c++

菜狗现在才开始备战蓝桥杯QAQ

【蓝桥杯专题】 （C++ | 洛谷 | acwing | 蓝桥）

• 贪心题 建议 整理同类型 然后背过！

1055. 股票买卖 II

链接 链接

• 思路 ： 能卖就卖 累加和
• 可证明

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e5 + 10;

int a[N];

void solve () {
    int n;
    cin >> n;
    rep(i, 0, n - 1) {
        cin >> a[i];
    }
    int now = a[0] ;
    ll ans = 0;
    rep(i, 0, n - 2) {
        int dt = a[i + 1] - a[i];
        if(dt > 0) ans += dt;
    } 
    cout << ans << endl;

}

int main(void){
	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 3;
    // cin >> T;
	while(T --) solve();
	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

AcWing 104. 货仓选址

区间选点 ， 注意单数 还是 复数个节点
链接 链接

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e5 + 10;

int a[N];

void solve () {
    int n;
    cin >> n;
    rep(i, 0, n - 1) {
        cin >> a[i];
    }
    int mid = 0;
    if(n % 2 == 1) {
        mid =  n / 2;
    } else {
        mid = n / 2 - 1;
    }
    ll res = 0;
    rep(i, 0, n - 1) {
        res += abs(a[mid] - a[i]);
    }
    cout << res << endl;
}

int main(void){
	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
    // cin >> T;
	while(T --) solve();
	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

传递糖果

链接 链接

建议 ： https://www.acwing.com/solution/content/28451/

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e6 + 10;


ll a[N], c[N];

void solve () {
    int n ;
    ll sum = 0;
    cin >> n;
    rep (i, 1, n ) {
        cin >> a[i];
        sum += a[i];
    }
    // cout << sum << endl;
    int a_ = sum / n;

   
    // cout << a_ << endl;
    for(int i = n; i > 1; i --) { // dijian
        c[i] = c[i + 1] + a_ - a[i];
    }
    c[1] = 0;
    sort(c + 1, c + n + 1);

    ll res = 0;
    rep(i, 1, n) {
        res += abs(c[i] - c[(i + 1) / 2]);
    }
   
    cout << res << endl;
}

int main(void){
	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
    // cin >> T;
	while(T --) solve();
	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
49
50
51
52
53
54
55
56

AcWing 112. 雷达设备

链接 链接

• 思路 ： 重载sort函数 ，对每个节点 映射到对应区间， 最后对所以区间就行判断， 重复就不选 ， 选就cnt ++

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e3 + 10;

struct segement {
    double l, r;
    bool operator < (const segement & t) {
        return r < t.r;
    }
}seg[N];

void solve () {
    int n , d;
    bool flag = false;
    cin >> n >> d;
    rep(i, 1, n) {
        int x, y;
        cin >> x >> y;
        if (y > d) {
            flag = true;
        } else {
            double len = sqrt(d * d - y * y);
            seg[i].l = x - len, seg[i].r = x + len;
        }
    }
    if (flag) {
        cout << "-1" << endl;
        return;
    } else {
        sort(seg + 1, seg + n + 1);
        int cnt = 0;
        double last = -1e20;
        rep(i, 1, n) {
            if(last < seg[i].l) {
                cnt ++ ;
                last = seg[i].r;
            }
        }
        cout << cnt << endl;
    }
}

int main(void){
	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
    // cin >> T;
	while(T --) solve();
	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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

付账问题

题目链接

• 存在问题 ： 如果要使用 scanf printf就别使用 cin cout
  
  
  

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
// typedef long long ll;
// typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
// const int N = 5* 1e5 + 10;

int a[5000010];
int n;

void solve () {
//   int n;
    long double s;
    scanf("%d%LF", &n, &s);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);
    long double res = 0, avg = s / n;
    for (int i = 0; i < n; i ++ )
    {
        double cur = s / (n - i);
        if (a[i] < cur) cur = a[i];
        res += (cur - avg) * (cur - avg);
        s -= cur;
    }

    printf("%.4Lf\n", sqrt(res / n));
    // cout << sqrt(res / n) << endl;
}

int main(void){
// 	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
    // cin >> T;
	while(T --) solve();
	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

乘积最大

• 取模的数 正负不会 影响结果的
• 在 C++ 直接取模即可
• 分情况讨论 : 除了负数那个 其他情况全为正（因为如果最大数都为负数的话，那么就代表全为负数） 直接取就可以

链接 链接

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+9;
const int N = 1e5 + 10;

int a[N];

void solve () {
	int n, k;
    cin >> n >> k;
    rep(i, 0, n - 1) {
        cin >> a[i];
    }  
    sort(a, a + n);
    int l = 0 ,r = n - 1;
    int sign = 1;
    int res = 1;

    if(k % 2) {
        res *= a[r --];
        k --;
        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; 
            l += 2;
        } else{
            res = y % mod * res % mod;
            r -= 2;
        }
        k -=2;
    }
    cout << res << endl;
}
 

int main(void){
// 	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
    // cin >> T;
	while(T --) solve();
	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
49
50
51
52
53
54
55
56
57
58
59
60

AcWing 1247. 后缀表达式

链接 链接

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 2 * 1e5 + 10;

int a[N];

void solve () {
    int n, m;
    cin >> n >> m;
    int k = n + m + 1;
    rep(i, 0, k - 1) {
        cin >> a[i];
    }
    ll res = 0;

    if(!m) {
        rep(i,0,k - 1)res += a[i];
    } else {
        sort(a, a + k );
        res += a[k - 1] - a[0];
        rep(i, 1, k - 2) {
            res += abs(a[i]);
        }
    }

    
    cout << res << endl;
}

int main(void){
// 	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
    // cin >> T;
	while(T --) solve();
	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
49
50
51

凑数 （acc杯）

• 当 n 是偶数时，每次除 2，不需要代价。
• 当 n 是奇数时，需要花 1 点代价变成偶数。
  链接 链接

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,  int> PII;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back
#define endl "\n"
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N  = 100010;
const int M = N * 2;
#define x first
#define y second

int a[16] = {0,1,1,2,0,2,2,3,0,2,2,3,2,3};
void solve () {
	ll ans = 0;
	int x;
	cin >> x;
    while(x) {
        if(x % 2 == 1) ans ++;
        x /= 2;
    }
    cout << ans <<endl;
}

int main(void){
// 	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
    // cin >> T;
	while(T --) solve();
	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