当前位置：首页 > article >正文

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

article 2025/1/13 17:33:09

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

在这里插入图片描述

文章目录

【蓝桥杯专题】（C++ | 洛谷 | acwing | 蓝桥）
1055. 股票买卖 II
AcWing 104. 货仓选址
传递糖果
AcWing 112. 雷达设备
付账问题
乘积最大
AcWing 1247. 后缀表达式
P

【蓝桥杯专题】（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;
}

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;
}

传递糖果

链接链接

建议： 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;
}

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;
}

付账问题

题目链接

存在问题：如果要使用 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;
}

乘积最大

取模的数正负不会影响结果的
在 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;
}

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;
}