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

算法-贪心算法

news 来源：原创 2025/7/6 13:52:29

圣诞老人的礼物-Santa Clau’s Gifts

现在有多箱不同的糖果，每箱糖果有自己的价值和重量，每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿雪橇最多只能装下重量W的糖果，请问圣诞老人最多能带走多大价值的糖果。

输入

第一行由两个部分组成，分别为糖果箱数正整数n(1 <= n <= 100)，驯鹿能承受的最大重量正整数w（0 < w < 10000），两个数用空格隔开。其余n行每行对应一箱糖果，由两部分组成，分别为一箱糖果的价值正整数v和重量正整数w，中间用空格隔开。

输出

输出圣诞老人能带走的糖果的最大总价值，保留1位小数。输出为一行，以换行符结束。

解法：

按礼物的价值/重量比从大到小依次选取礼物，对选取的礼物尽可能多地装，直到达到总重量w

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const double eps = 1e-6;
//定义一个结构体Candy，包含两个成员变量v和w
struct Candy {int v; int w;//重载小于运算符，用于排序bool operator < (const Candy & c) const {return  double(v)/w - double(c.v)/c.w > eps;}
} candies[110];
int main() {int n,w;//读取输入的n和wscanf("%d%d",&n,&w);//读取每个糖果的v和wfor(int i = 0;i < n; ++i)scanf("%d%d", &candies[i].v , &candies[i].w);//对糖果按照v/w的值进行排序sort(candies,candies+n);int totalW = 0;double totalV = 0;//遍历每个糖果for(int i = 0;i < n; ++i) {//如果当前糖果的重量加上总重量不超过wif( totalW + candies[i].w <= w) {totalW += candies[i].w;totalV += candies[i].v;}//否则，将剩余的重量全部用来装当前糖果else {totalV += candies[i].v *double(w-totalW)/candies[i].w;break;}}//输出总价值printf("%.1f",totalV);return 0;
}

输入

4 15
100 4

412 8
266 7
591 2
输出

1193.0

电影节

给定每部电影的放映时间区间，区间重叠的电影不可能同时看（端点可以重合），问李雷最多可以看多少部电影。

输入

多组数据。每组数据开头是n(n<=100)，表示共n场电影。接下来n行，每行两个整数(均小于1000），表示一场电影的放映区间 n=0则数据结束

输出

对每组数据输出最多能看几部电影

贪心解法

对电影结束时间进行从早到晚的排序，然后尽量选取结束早的电影看，以节省时间看后面的更多的电影。具体的操作方法是：对按结束时间排序后的电影从早到晚一个个遍历，若当前遍历到的这部电影的结束时间早于下一部电影的开始时间，则sum++（sum初始化为1，因为显然最少可以看一部电影），若当前遍历到的这部电影的结束时间完于下一部电影的开始时间，则看当前这部，不看下一部电影了（原因：对于重合的两场电影，当然选择结束早的，为后面留下更多的时间，这就是一种贪心思想）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{int begin,end;//记录开始时间和结束时间
}a[105];int cmp(node a,node b)
{return a.end<b.end;//按结束时间由小到大排序
}int main()
{int t;while((cin>>t)&&(t!=0))//数据组数{for(int i=0;i<t;i++){scanf("%d%d",&a[i].begin,&a[i].end);//依次输入数据}sort(a,a+t,cmp);//排序int sum=1;//最少看的电影书肯定是1int js;//表示结束时间js=a[0].end;for(int i=1;i<t;i++)//依次遍历{if(a[i].begin>=js)//如果下一场开始的时间在这一场结束时间之后，就满足要求{js=a[i].end;//更新结束时间的值sum++;//可以看电影的个数+1}}printf("%d\n",sum);}
}

输入

3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
0

输出

3

Stall Reservations

有n头牛（1<=n<=50,000)要挤奶。给定每头牛挤奶的时间区间[A,B] (1<=A<=B<=1,000,000，A,B为整数)。牛需要呆畜栏里才能挤奶。一个畜栏同一时间只能容纳一头牛。问至少需要多少个畜栏，才能完成全部挤奶工作，以及每头牛都放哪个畜栏里（Special judged) 去同一个畜栏的两头牛，它们挤奶时间区间哪怕只在端点重合也是不可以的。

贪心解法：

所有奶牛都必须挤奶。到了一个奶牛的挤奶开始时间，就必须为这个奶牛找畜栏。因此按照奶牛的开始时间逐个处理它们，是必然的。

S(x)表示奶牛x的开始时间。E(x)表示x的结束时间。对E(x), x可以是奶牛，也可以是畜栏。畜栏的结束时间，就是正在其里面挤奶的奶牛的结束时间。同一个畜栏的结束时间是不断在变的。

1：把奶牛按照挤奶开始时间从前往后排序
2：为第一头奶牛分配畜栏
3：依次处理后面的每一头奶牛，处理第i头奶牛时候，考虑已分配畜栏中结束时间最早的畜栏x。
若E(x) < S(i), 则不用分配新畜栏，i可进入x,并修改E(x)为E(i)

若E(x) >= S(i)，则分配新畜栏y,记 E(y) = E(i)
直到所有奶牛处理结束。

需要用优先队列存放已经分配的畜栏，并使得结束时间最早的畜栏始终位于队列头部。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct Cow {//奶牛int a, b; //挤奶区间起终点int No; //编号bool operator<(const Cow& c) const {return a < c.a;//按照开始时间从早到晚排序}
} cows[50100];
int pos[50100]; //pos[i]表示编号为i的奶牛去的畜栏编号
struct Stall {//畜栏int end; //结束时间int No; //编号bool operator<(const Stall& s) const {return end > s.end;//按照畜栏的结束时间排序}Stall(int e, int n) :end(e), No(n) { }
};
int main()
{int n;cin>>n;for (int i = 0; i < n; ++i) {cin>>cows[i].a>>cows[i].b;cows[i].No = i;}sort(cows, cows + n);int total = 0;priority_queue<Stall> pq;//畜栏的队列for (int i = 0; i < n; ++i) {if (pq.empty()) {//如果畜栏为空的话，就是放入第一个畜栏++total;pq.push(Stall(cows[i].b, total));//并且新开一个畜栏，以放入当前奶牛的结束时间为畜栏的结束时间pos[cows[i].No] = total;}else {Stall st = pq.top();//指向队列的顶端，即即将释放的畜栏if (st.end < cows[i].a) { //端点也不能重合如果畜栏的结束时间早于奶牛的开始时间的话pq.pop();pos[cows[i].No] = st.No;pq.push(Stall(cows[i].b, st.No));}else { //对应 if( st.end < cows[i].a //畜栏的结束时间晚于奶牛的开始时间，即队列中没有可以释放的畜栏，就新开一个畜栏放入奶牛++total;pq.push(Stall{cows[i].b,total });//畜栏结束时间设置为奶牛结束pos[cows[i].No] = total;}}}cout << total << endl;for (int i = 0; i < n; ++i)cout << pos[i] << endl;return 0;
}

输入

5
1 10
2 4
3 6
5 8
4 7

输出
4
1
2
3
2
4

Radar Installation

x轴是海岸线，x轴上方是海洋。海洋中有n （1<=n<=1000)个岛屿，可以看作点。给定每个岛屿的坐标（x,y)，x,y 都是整数。当一个雷达（可以看作点）到岛屿的距离不超过d(整数），则认为该雷达覆盖了该岛屿。雷达只能放在x轴上。问至少需要多少个雷达才可以覆盖全部岛屿。

对每个岛屿P,可以算出，覆盖它的雷达，必须位于x轴上的区间[Ps,Pe]。如果有雷达位于某个x轴区间 [a,b]，称该雷达覆盖此区间。问题转换为，至少要在x轴上放几个雷达（点），才能覆盖全部区间[P1s,P1e],[P2s,P2e]....[Pns,Pne]。

如果可以找到一个雷达同时覆盖多个区间，那么把这多个区间按起点坐标从小到大排序，则最后一个区间(起点最靠右的)k的起点，就能覆盖所有区间

将所有区间按照起点从小到大排序，并编号0 -(n-1)
依次考察每个区间的起点，看要不要在那里放雷达。开始，所有区间都没被覆盖，所以目前编号最小的未被覆盖的区间的编号firstNoConverd= 0
考察一个区间 i 的起点xi的时候，要看从firstNoCovered 到区间i 1 中是否存在某个区间c ,没有被xi 覆盖。如果没有，则先不急于在xi放雷达，接着往下看。如果有，那么c 的终点肯定在xi的左边，因此不可能用同一个雷达覆盖c 和i。即能覆盖c的点，已经不可能覆盖i和i后面的区间了。此时，为了覆盖c，必须放一个雷达了，放在区间i-1 的起点即可覆盖所有从firstNoCovered到 i-1的区间。因为当初考察 i-1的起点 z 时候，并没有发现z 漏覆盖了从firstNoCovered 到i-2 之间的任何一个区间
放完雷达后，将firstNoCovered改为i，再做下去。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
struct dao
{double x ,y;
}da[10000];
bool cmp(dao a,dao b)//排序
{if(a.y==b.y)return a.x>b.x;return a.y<b.y;
}
int main()
{int n,d;double x1,y1;int ans;int k=0;while(scanf("%d%d",&n,&d)&&n||d){ans=1;for(int i=0;i<n;i++){scanf("%lf%lf",&x1,&y1);da[i].x=x1-sqrt((double)d*(double)d-(double)y1*y1);da[i].y=x1+sqrt((double)d*(double)d-(double)y1*y1);if((d-y1)<0||d<0)ans=-1;}if(ans==-1){printf("Case %d: -1\n",++k);continue;}else{double t1;sort(da,da+n,cmp);t1= da[0].y;for(int i=1; i<n ; i++)if(da[i].x>t1){  ans++;t1 = da[i].y;//更新右范围}printf("Case %d: %d\n",++k, ans);}}
}

输入

3 2
1 2
-3 1
2 1

输出
Case 1: 2

圣诞老人的礼物-Santa Clau’s Gifts

电影节

Stall Reservations

Radar Installation

相关文章：