贪心算法 - 信奥网|信息学奥赛

0推荐

957浏览

信息学奥赛一本通T1432：贪心算法糖果传递

【题目描述】有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。【输入】第一行一个正整数n≤1000000，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．【输出】求使所有人获得均等糖果的最小代价。【输入样例】4【输出样例】4【源程序】

0
轩爸发布于 2020-05-19 16:20

1推荐

830浏览

信息学奥赛一本通T1431：贪心算法钓鱼

【题目描述】在一条水平路边，有 nn 个钓鱼湖，从左到右编号为 1,2,…,n。佳佳有 HH 个小时的空余时间，他希望利用这个时间钓到更多的鱼。他从 1 出发，向右走，有选择的在一些湖边停留一定的时间（是 55 分钟的倍数）钓鱼。最后在某一个湖边结束钓鱼。佳佳从第 i 个湖到第 i+1 个湖需要走 5×Ti分钟路，还测出在第 i 个湖停留，第一个 5 分钟可以钓到 Fi 条鱼，以后每再钓 5

0
轩爸发布于 2020-05-19 16:20

0推荐

920浏览

信息学奥赛一本通T1430：贪心算法家庭作业

【题目描述】老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10，要求在6天内交，那么要想拿到这10学分，就必须在第6天结束前交。每个作业的完成时间都是只有一天。例如，假设有7次作业的学分和完成时间如下：作业号 1 2 3 4 5 6 7最多可以获得15学分，其

0
轩爸发布于 2020-05-19 16:20

1推荐

1020浏览

信息学奥赛一本通T1429：贪心算法线段

【题目描述】在一个数轴上有n条线段，现选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少?【输入】第一行为一个正整数n，下面n行每行2个数字ai，bi,描述每条线段。【输出】输出文件仅包括1个整数，为k的最大值。【输入样例】3【输出样例】2【源程序】

0
轩爸发布于 2020-05-19 16:20

0推荐

829浏览

信息学奥赛一本通T1428：贪心算法数列分段

【题目描述】对于给定的一个长度为N的正整数数列A[i]，现要将其分成连续的若干段，并且每段和不超过M（可以等于M），问最少能将其分成多少段使得满足要求。【输入】第1行包含两个正整数N，M，表示了数列A[i]的长度与每段和的最大值；第2行包含N个空格隔开的非负整数A[i]，如题目所述。【输出】一个正整数，输出最少划分的段数。【输入样例】5 6 【输出样例】3【源程序】

0
轩爸发布于 2020-05-19 10:20

0推荐

814浏览

信息学奥赛一本通T1427：贪心算法数列极差

【题目描述】在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max−min。【输入】第一行，一个数为N;第二行，N个数。【输出】输出极差。【输入样例】3【输出样例】2【源程序】

0
轩爸发布于 2020-05-19 10:20

0推荐

746浏览

信息学奥赛一本通T1426：贪心算法智力大冲浪

【题目描述】小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则：首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数

0
轩爸发布于 2020-05-19 10:20

0推荐

849浏览

【题目描述】某工厂收到了 n 个产品的订单，这 n 个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。某个产品 i 在 A，B 两车间加工的时间分别为Ai,Bi。怎样安排这 n 个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A，B 两车间加工完毕的时间。【输入】第一行仅—个数据 n ，表示产品的数

0
轩爸发布于 2020-05-19 10:20

1推荐

675浏览

信息学奥赛一本通T1424：贪心算法喷水装置

【题目描述】长L 米，宽 WW 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？【输入】输入包含若干组测试数据。第一行一个整数 T 表示数据组数；每组数据的第一行是整数 n、L 和 W；接下来的 n 行，每行包含两个整数，给出一个喷头

0
轩爸发布于 2020-05-19 10:20

0推荐

959浏览

信息学奥赛一本通T1423：贪心算法种树

【题目描述】现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。门口路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民房子门前被指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。

0
轩爸发布于 2020-05-18 16:20

0推荐

836浏览

信息学奥赛一本通T1422：贪心算法活动安排

【题目描述】设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交,则称活动ii与活动jj是相容的。也就是说，当si≥fj或sj≥

0
轩爸发布于 2020-05-18 16:20

0推荐

893浏览

信息学奥赛一本通T1324：贪心算法整数区间

【题目描述】请编程完成以下任务：1.从文件中读取闭区间的个数及它们的描述；2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。【输入】首行包括区间的数目n,1≤n≤10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0≤a≤b≤10000,它们是某一个区间的开始值和结束值。【输出】第一行集合元素的个数,对于每一个区间都至少有一个整数属

0
轩爸发布于 2020-05-09 16:20

0推荐

1013浏览

信息学奥赛一本通T1323：贪心算法活动选择

【题目描述】学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。【输入】第一行一个整数n(n≤1000)；接下来的n行，每行两个整数，第一个begini，第二个是endi(begini<endi≤32767)。【输出】输出最多能安排的活动个数。【输入样例】11【输出样例

0
轩爸发布于 2020-05-09 16:20

0推荐

1652浏览

信息学奥赛一本通T1322：贪心算法拦截导弹问题

【题目描述】某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。【输入】n颗依

0
轩爸发布于 2020-05-09 16:20

0推荐

1343浏览

信息学奥赛一本通T1321：贪心算法删数问题

【题目描述】输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。输出新的正整数。（n不超过240位）输入数据均不需判错。【输入】n 和 s【输出】一个正整数，即最少需要的组数。【输入样例】175438【输出样例】13【源程序】

0
轩爸发布于 2020-05-09 16:20