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

菜狗现在才开始备战蓝桥杯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
    image-20230317102140385
    image-20230317104102603
    image-20230317104130045
#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++ 直接取模即可
  • 分情况讨论 : 除了负数那个 其他情况全为正（因为如果最大数都为负数的话，那么就代表全为负数） 直接取就可以

image-20230317115100757
链接 链接

#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. 后缀表达式

image-20230317115009444
链接 链接

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

P

链接 链接

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/1025.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Flink 应用案例——求网页访问量Top N 实时计算（附可执行代码）

Flink 应用案例——求网页访问量Top N 实时计算（附可执行代码）

在学习了Flink之后&#xff0c;笔者通过以下案例对Flink API 进行简单复习 目录 案例要求 前置准备 编写主程序&#xff08;点此跳转至代码&#xff09; 运行截图 案例要求 以下数据 为某网站的访问日志 现要求通过以下数据 统计出最近10s内最热门的N个页面&#xff08;即…
阅读更多...
【3.17】MySQL索引整理、回溯（分割、子集问题）

【3.17】MySQL索引整理、回溯（分割、子集问题）

3.1 索引常见面试题 索引的分类 什么是索引&#xff1f; 索引是一种数据结构&#xff0c;可以帮助MySQL快速定位到表中的数据。使用索引&#xff0c;可以大大提高查询的性能。 按「数据结构」分类&#xff1a;Btree索引、Hash索引、Full-text索引。 InnoDB 存储引擎创建的聚簇…
阅读更多...
漫画：什么是快速排序算法？

漫画：什么是快速排序算法？

这篇文章&#xff0c;以对话的方式&#xff0c;详细着讲解了快速排序以及排序排序的一些优化。 一禅&#xff1a;归并排序是一种基于分治思想的排序&#xff0c;处理的时候可以采取递归的方式来处理子问题。我弄个例子吧&#xff0c;好理解点。例如对于这个数组arr[] { 4&…
阅读更多...
优思学院｜六西格玛DMAIC，傻傻搞不清？

优思学院｜六西格玛DMAIC，傻傻搞不清？

DMAIC还是搞不清&#xff1f; DMAIC是一个用于过程改进和六西格玛的问题解决方法论。它是以下五个步骤的缩写&#xff1a; 定义&#xff08;Define&#xff09;&#xff1a;明确问题&#xff0c;设定项目的目标和目的。绘制流程图&#xff0c;并收集数据&#xff0c;以建立未来…
阅读更多...
基于bearpi的智能小车--Qt上位机设计

基于bearpi的智能小车--Qt上位机设计

基于bearpi的智能小车--Qt上位机设计 前言一、界面原型1.主界面2.网络配置子窗口模块二、设计步骤1.界面原型设计2.控件添加信号槽3.源码解析3.1.网络链接核心代码3.2.网络设置子界面3.3.小车控制核心代码总结前言 最近入手了两块小熊派开发板，借智能小车案例，进行鸿蒙设备学…
阅读更多...
01背包问题c++

01背包问题c++

问题 问题介绍 有 N 种物品和一个容量是 V 的背包&#xff0c;每种物品都有无限件可用。 第 i 种物品的体积是 vi&#xff0c;价值是 wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输出最大价值。 输入格式 第…
阅读更多...
基于Transformer的交通预测模型部分汇总【附源代码】

基于Transformer的交通预测模型部分汇总【附源代码】

交通预测一直是一个重要的问题&#xff0c;它涉及到交通运输系统的可靠性和效率。随着人工智能的发展&#xff0c;越来越多的研究者开始使用深度学习模型来解决这个问题。其中&#xff0c;基于Transformer的交通预测模型在近年来备受关注&#xff0c;因为它们具有优秀的建模能力…
阅读更多...
设计模式之桥接模式(C++)

设计模式之桥接模式(C++)

作者&#xff1a;翟天保Steven 版权声明&#xff1a;著作权归作者所有&#xff0c;商业转载请联系作者获得授权&#xff0c;非商业转载请注明出处 一、桥接模式是什么&#xff1f; 桥接模式是一种结构型的软件设计模式&#xff0c;将抽象部分与实现部分分离&#xff0c;使他们可…
阅读更多...
像ChatGPT玩转Excel数据

像ChatGPT玩转Excel数据

1.引言 最近ChatGPT的出现&#xff0c;把人工智能又带起了一波浪潮。机器人能否替代人类又成了最近热门的话题。 今天我们推荐的一个玩法和ChatGPT有点不一样。我们的课题是“让用户可以使用自然语言从Excel查询到自己想要的数据”。 要让自然语言可以从Excel中查数据&#…
阅读更多...
通过百度文心一言大模型作画尝鲜，感受国产ChatGPT的“狂飙”

通过百度文心一言大模型作画尝鲜，感受国产ChatGPT的“狂飙”

3月16日下午&#xff0c;百度于北京总部召开新闻发布会&#xff0c;主题围绕新一代大语言模型、生成式AI产品文心一言。百度创始人、董事长兼首席执行官李彦宏&#xff0c;百度首席技术官王海峰出席&#xff0c;并展示了文心一言在文学创作、商业文案创作、数理推算、中文理解、…
阅读更多...
用Qt画一个温度计

用Qt画一个温度计

示例1 以下是用Qt绘制一个简单的温度计的示例代码&#xff1a; #include <QPainter> #include <QWidget> #include <QApplication> class Thermometer : public QWidget { public:Thermometer(QWidget *parent 0); protected:void paintEvent(QPaintEvent …
阅读更多...
【Hive】配置

【Hive】配置

目录 Hive参数配置方式 参数的配置方式 1. 文件配置 2. 命令行参数配置 3. 参数声明配置 配置源数据库 配置元数据到MySQL 查看MySQL中的元数据 Hive服务部署 hiveserver2服务 介绍 部署 启动 远程连接 1. 使用命令行客户端beeline进行远程访问 metastore服务 …
阅读更多...
LC-146.LRU 缓存

LC-146.LRU 缓存

题解&#xff1a;https://leetcode.cn/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/ 文章目录[146. LRU 缓存](https://leetcode.cn/problems/lru-cache/)思路从0开始实现使用LinkedHashMap实现拓展&#xff1a;[460. LFU 缓存](https://leet…
阅读更多...
【2024考研】计算机考研，4轮复习时间安排

【2024考研】计算机考研，4轮复习时间安排

文章目录&#x1f3a8;第1轮复习&#xff08;暑假前&系统课&#xff09;英语1/2数学1/2专业课408&#x1f3a8;第2轮复习&#xff08;开学前&真题&#xff09;英语1/2试卷数学1/2试卷专业课408试卷&#x1f3a8;第3轮复习&#xff08;报名前&政治&#xff09;政治试…
阅读更多...
什么是数据治理，如何保障数据质量？_光点科技

什么是数据治理，如何保障数据质量？_光点科技

随着信息化和数据化的发展&#xff0c;数据已经成为企业最为重要的资产之一。数据治理作为一种管理和保障数据质量的方法&#xff0c;越来越受到企业的重视。什么是数据治理&#xff1f;数据治理是一种管理和保障数据质量的方法。数据治理的主要目的是确保数据的可靠性、准确性…
阅读更多...
Android APP隐私合规检测工具Camille使用

Android APP隐私合规检测工具Camille使用

目录一、简介二、环境准备常用使用方法一、简介 现如今APP隐私合规十分重要&#xff0c;各监管部门不断开展APP专项治理工作及核查通报&#xff0c;不合规的APP通知整改或直接下架。camille可以hook住Android敏感接口&#xff0c;检测是否第三方SDK调用。根据隐私合规的场景&a…
阅读更多...
二、数据结构-线性表

二、数据结构-线性表

目录 &#x1f33b;&#x1f33b;一、线性表概述1.1 线性表的基本概念1.2 线性表的顺序存储1.2.1 线性表的基本运算在顺序表上的实现1.2.2 顺序表实现算法的分析1.2.3 单链表类型的定义1.2.4 线性表的基本运算在单链表上的实现1.3 其他运算在单链表上的实现1.3.1 建表1.3.2 删除…
阅读更多...
Adam优化器算法详解及代码实现

Adam优化器算法详解及代码实现

文章目录学习率调整与梯度估计修正RMSprop 算法动量法Adam学习率调整与梯度估计修正 在介绍Adam算法之前&#xff0c;先谈谈Adam中两个关键的算法&#xff1a;学习率调整&#xff08;RMSprop 算法&#xff09;与梯度估计修正。 RMSprop 算法 学习率是神经网络优化时的重要超…
阅读更多...
计算机组成原理（3）-哈工大

计算机组成原理（3）-哈工大

概述存储器分类按存储介质分类第一个是易失的&#xff0c;后面三个是非易失的按存取方式分类按在计算机中的作用分类RAM可读可写 ROM只读存储器的层次结构存储器的三个主要特性的关系缓存-主存层次和主存-辅存层次时间局部性就是cpu访问了一个数据&#xff0c;在不久的将来可能…
阅读更多...
python学习——【第六弹】

python学习——【第六弹】

前言 上一篇文章 python学习——【第五弹】中我们了解了python中的不可变序列元组&#xff0c;这篇文章接着介绍可变序列 字典。 字典 字典的实现原理&#xff1a; 字典&#xff0c;顾名思义其实现原理和字典类似&#xff0c;字典中的元素都是key—value&#xff0c;以键值对…
阅读更多...
最新文章

Copyright @ 2022~2023