首页 > 编程语言 >贪心算法

贪心算法

时间:2023-05-24 13:11:40浏览次数:47  
标签:int res ++ ran 算法 heap using 贪心

//区间选点
//数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)
//
//Input
//第一行1个整数N(N<=100)
//第2~N+1行,每行两个整数a,b(a,b<=100)
// INPUT :2
//1 5
//4 6
//OUT PUT:1
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
struct range
{
    int l,r;
    bool operator<(const range &w)const
    {
        return r<w.r;
    }
}ran[N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        ran[i]={l,r};
    }
    sort(ran,ran+n);
    int res=0,ed=-2e9;
    for(int i=0;i<n;i++)
        if(ed<ran[i].l)
    {
        res++;
        ed=ran[i].r;
    }
    cout<<res;
    return 0;
}
//区间数组(使用小根堆)
//给定N个闭区间[ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。
//输出最小组数。
//输入格式
//第一行包含整数N,表示区间数。
//接下来N行,每行包含两个整数ai,biai,bi,表示一个区间的两个端点。
//输出格式
//输出一个整数,表示最小组数。
//数据范围
//1≤N≤105
//−109 ≤ ai ≤ bi ≤ 109
//输入样例:
//3
//-1 1
//2 4
//3 5
//输出样例:
//2
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    // 重载<,按左端点排序
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    // 用小根堆维护所有组的右端点的最大值
    // 堆中的每一个值存的是每个组的右端点的最大值
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i ++ )
    {
        // 如果堆为空或者堆的最小右端点 >= 现在区间的左端点,则说明有交集,不能合并,需要新开一个堆
        if (heap.empty() || heap.top() >= range[i].l) heap.push(range[i].r);
        // 否则说明至少与最小的右端点的组没有交集,将它放到右端点最小的组里去
        else
        {
            heap.pop(); // 弹出这个区间的最小右端点,插入当前区间的右端点,即将其更新了
            heap.push(range[i].r);
        }
    }
    // 输出组的数量
    printf("%d\n", heap.size());

    return 0;
}
//合并果子
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    priority_queue<int,vector<int>,greater<int> >heap;//构建小根堆
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        heap.push(x);//将输入的果子数放入到小根堆中,此时最小的果子数会自动排序到上面
    }
    int res=0;
    while(heap.size()>1)//当堆中的节点数>1时
    {
        int a=heap.top();heap.pop();//取第一个最小的数,然后删除
        int b=heap.top();heap.pop();//同理
        res+=a+b;//二者相加
        heap.push(a+b);//将加完之后的结果存放在小根堆中
    }
    cout<<res<<endl;
}
//现在各大 oj 上有 n 个比赛,每个比赛的开始、结束的时间点是知道的。
//yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。
//所以,他想知道他最多能参加几个比赛。
//由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加2 个及以上的比赛。
//输入格式
//第一行是一个整数n ,接下来 n 行每行是2 个整数,表示比赛开始、结束的时间。
//
//输出格式
//一个整数最多参加的比赛数目。
//
//输入输出样例
//输入
//3
//0 2
//2 4
//1 3
//输出
//2
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
struct range
{
    int l,r;
    bool operator<(const range &m)const
    {
        return r<m.r;
    }
}ran[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        ran[i]={l,r};
    }
    sort(ran,ran+n);
    int st=ran[0].l,ed=ran[0].r,res=1;
    for(int i=0;i<n;i++)
    {
            if(ran[i].l>=ed)
            {
                ed=ran[i].r;
                res++;
            }
    }
    cout<<res;
    return 0;
}
//建立雷达
//http://bailian.openjudge.cn/practice/1328
///本质还是贪心的区间选点,一开始的思路错了,写了一个小时的代码还是不会做
///去看题解发现,可以把每个点都变成一个圆,然后在x轴上取交点
///那么我们是不是可以这样想
///因为每一个点都需要被覆盖,所以我们需要让每一个点扩充成一个半径是/雷达可以覆盖的半径/的圆
///然后再把每一个圆与x轴的交点坐标算出来
///这样我们就成功的把这道题转换成了线段覆盖的问题
///再把产生的数据按照末尾的结束顺序排序,再在每一个没有访问过的节点的末尾放置一个雷达即可
#include <bits/stdc++.h>
using namespace std;
struct node
{
    double l,r;
}a[1005];
int n,r,num;
int cmp(node a, node b)
{
    if(a.r==b.r) return a.l<b.l;
    return a.r<b.r;
}
int main()
{
    while(cin>>n>>r)
    {
        if(n+r==0) break;
        int x,y;
        int f = 0;
        for(int i=1;i<=n;i++)
        {
            cin >>x>>y;
            if(y>r) f = 1;
            double d = sqrt(r*r-y*y);///规划成区间
            a[i].l=x-d;a[i].r=x+d;
        }
        if(f)
        {
            printf("Case %d:-1\n",++num);
            continue;
        }
        sort(a+1,a+n+1,cmp);
        double last=a[1].r;
        int cnt=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i].l>last)
            {
                cnt++;
                last=a[i].r;
            }
        }
        printf("Case %d:%d\n",++num,cnt);
    }
    return 0;
}
//田忌赛马
//https://blog.csdn.net/weiainibuqi/article/details/106602305?ops_request_misc=&request_id=&biz_id=102&utm_term=%E7%94%B0%E5%BF%8C%E8%B5%9B%E9%A9%AC&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-3-106602305.142^v86^control,239^v2^insert_chatgpt&spm=1018.2226.3001.4187
///使用磨墨战
///从大到小排序
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    while(cin>>n&&n!=0)
    {
        int a[n+1],b[n+1];
        int a1=1,b1=1,a2=n,b2=n,res=0;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        sort(a+1,a+1+n,cmp);
        sort(b+1,b+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            if(a[a1]>b[b1])///先对比上等马,如果田忌最快的马比王的还快,那就要拿下200;
            {
                res+=200;
                a1++,b1++;
            }
           else if(a[a2]>b[b2])///如果没他快,再对比最慢的马
            {
                res+=200;
                a2--,b2--;
            }
           else if(a[a2]<b[b1])///如果两个都拿不下,咱只能用下等马对上等马来干他
            ///这里有可能出现两者相等,此时王是最快的马,如果王最快的马等于田忌最慢的马,再和第二个if对比,那就是王就一个马了,不用做文章;
           {
               res-=200;
               a2--;
               b1++;
           }
        }
        cout<<res<<endl;
    }
    return 0;
}
//小明准备去钓鱼,他准备在一个有 $n$ 个湖的地方钓 $h$ 小时,小明只能按顺序从第 1 个湖 开始,依次在各个湖钓鱼,但是在每个湖的钓鱼时间是由小明自己决定的。
//从第 $i$ 个湖走到第 $i+1$ 个湖的时间是 $t_i$ 个 $5$ 分钟。例如 $t_3 = 4,$ 表明从第 $3$ 个湖走到第 $4$ 个湖需要 $20$ 分钟。
//对于每个湖 $i$ ,在初始的 $5$ 分钟,小明可以钓到 $f_i$ 条鱼,之后每过 $5$ 分钟,可钓到的鱼会 减少 $d_i$, 直到减少为 $0$ 。
//如果当前没有在湖中钓鱼,那么可以钓到的鱼的数量是不变的。
//假设 当前只有小明在钓鱼,请问如果规划钓鱼的安排,使得能钓上的鱼最多? 小明在每个湖的钓鱼时间必须是 $5$ 分钟的倍数。
#include<bits/stdc++.h>
using namespace std;
const int N=100;
struct node
{
    int f,d,num;
    bool operator<(const node &w)const///重载小于号
    {
        if(f==w.f) return num>w.num;///如果能钓的鱼都相等,那么靠左的湖排在前面
        else return f<w.f;
    }
}lake[N];
int n,h,a[N],cnt[N],dist[N];
int main()
{
    while(cin>>n&&n)
    {
        memset(dist,0,sizeof dist);///重置两湖之间的距离
        memset(a,0,sizeof a);
        memset(cnt,0,sizeof cnt);///cnt用来记录每个糊钓的次数
        int res=-1;
        cin>>h;
        h=h*12;
        for(int i=0;i<n;i++) {cin>>lake[i].f;lake[i].num=i;}
        for(int i=0;i<n;i++) cin>>lake[i].d;
        for(int i=1;i<=n-1;i++) {cin>>dist[i];dist[i]+=dist[i-1];}///算出dist
        priority_queue<node>que;
        for(int i=0;i<n;i++)///枚举从0-i个湖最大的钓鱼数
        {
            int ans=0;
            while(!que.empty()) que.pop();///清空队列
            memset(a,0,sizeof a);
            for(int j=0;j<=i;j++) que.push(lake[j]);///入队
            int t=h-dist[i];///算出钓鱼用的时间
            while(t>0)
            {
                node now=que.top();
                que.pop();
                t--;
                ans+=now.f;
                now.f=now.f-now.d;
                //cout<<a[now.num]<<endl;
                a[now.num]++;
                if(now.f<0) now.f=0;
                que.push(now);
            }
            if(ans>res)  ///记录当前的最优值以及方案
            {
                res=ans;
                for(int j=0;j<=i;j++) cnt[j]=a[j];
            }
        }
        for(int i=0;i<n-1;i++) cout<<cnt[i]*5<<", ";
        cout<<cnt[n-1]*5<<endl;
        cout<<"Number of fish expected: "<<res<<endl;
        cout<<endl;
    }
    return 0;
}

 

标签:int,res,++,ran,算法,heap,using,贪心
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17427998.html

相关文章

  • 算法学习 | 从几个有趣的故事说起,聊聊里面的算法
    前言提到故事我就来劲头了。一方面,我喜欢读故事、讲故事、搜集故事,另一方面,用讲故事的方式会为学习增加一些趣味性,有兴趣可以帮助坚持下去。下面要介绍的故事,有些大家应该不陌生。我之前有读到过,但是没有认真的研究过,有种熟悉的陌生感。今天分享读了的故事、研究了的解题过程、顺便......
  • Algorithm_01--C#递归算法
    ///递归算法本质:///1、方法的自我调用///2、有明确的终止条件///3、每次调用时,问题规模在不断减少。通过递减,最终到达终止条件  问题:程序在输入1000后(即1到1000的和),程序会出现异常。解答:百度后得出结论,栈溢出异常。1、递归......
  • TPSO-DSDT粒子群算法在三维装箱问题上的应用
    组合算法是将传统启发式算法与数学规划算法结合元启发式算法共同工作进行相应的计算,还有融合多种算法所获得的计算方法,结合了所有算法自身的有点,规避其自身缺点从而达到解决装箱问题的最终目的。现在,组合算法的整体规划绝大多数都是通过启发式算法完成的,局部优化的过程采用的是人......
  • 十大经典排序算法总结
    排序算法可以分为:内部排序:数据记录在内存中进行排序。外部排序:因排序的数据很大,内存不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序、计数排序、桶排序。其中比较类......
  • Day_01--C#递归算法
     ///递归算法本质:///1、方法的自我调用///2、有明确的终止条件///3、每次调用时,问题规模在不断减少。通过递减,最终到达终止条件 问题:程序在输入1000后(即1到1000的和),程序会出现异常。解答:百度后得出结论,栈溢出异常。1、递归方法在每......
  • 代码随想录算法训练营第十四天|144. 二叉树的前序遍历、145. 二叉树的后序遍历、94.
    【参考链接】1.满二叉树,完全二叉树,二叉搜索树(有数值,有序树)。2.平衡二叉搜索树:又被称为AVL(Adelson-VelskyandLandis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。3.优先级队列其实是一个堆,堆就是一棵完全二叉......
  • 算法刷题记录:NC22227 约瑟夫环
    题目链接https://ac.nowcoder.com/acm/problem/22227解题思路模拟环。这道题顺序数就行,顺序是逆时针,逆时针的箭头是往左拐的,变成直线后趋于正半轴所以是+。不过,这道模拟环并没有说从idx号开始,往左/右数几个人,所以不需要考虑+或-。因为不会越界,所以也不用额外%n。AC代码......
  • 基于PSO优化的SVM数据预测算法matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:     2.算法涉及理论知识概要         支持向量机(supportvectormachines,SVM)是二分类算法,所谓二分类即把具有多个特性(属性)的数据分为两类,目前主流机器学习算法中,神经网络等其他机器学习模型已经能很好完成二分......
  • m基于matlab的LDPC译码算法性能仿真,对比BP译码,最小和译码以及归一化偏移最小和译码
    1.算法仿真效果matlab2022a仿真结果如下:  2.算法涉及理论知识概要       LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农极限,且描述和......
  • 启发式算法在三维装箱问题上的应用
    启发式算法的出现时间比较难以确定,因为很多算法的提出都是在不同的领域和不同的时间段内,而且随着时间的推移,这些算法也在不断地完善和发展。以下是一些比较有代表性的启发式算法及其出现时间:1953年,模拟退火算法(SimulatedAnnealing,SA)模拟退火算法是一种基于固体物理学中固体退火......