怎样自学做网站,外贸网站制作设计,义乌网站备案,天津网络关键词排名#x1f36d; 大家好这里是清隆学长 #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f497; #x1f… 大家好这里是清隆学长 一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 在线评测链接
https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1073 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁
OJ题目截图 文章目录 在线评测链接OJ题目截图LYA的巡演题目描述输入格式输出格式样例输入样例输出样例解释数据范围题解题解参考代码 LYA的巡演
题目描述
LYA是一位歌手,她计划从 A A A 城市出发,在 T T T 天内到达 B B B 城市参加演出。途中,LYA会经过 N N N 座城市,每两座城市之间需要耗费一定的时间。LYA不能往回走,但可以在每座城市逗留卖唱赚钱。
LYA提前了解到,在一座城市卖唱第一天可以赚 M M M 元,之后每天的收入会减少 D D D 元,直到减为 0 0 0 为止。LYA只有在到达一座城市的第二天才能开始卖唱,如果当天卖过唱,就要等到第二天才能出发去下一座城市。
作为一位贪心的歌手,LYA希望在规定时间内赚到最多的钱。你能帮她算算最多能赚多少钱吗?
输入格式
第一行包含两个正整数 T T T 和 N N N,分别表示总天数和途中经过的城市数量,满足 0 T 1000 0 T 1000 0T1000, 0 N 100 0 N 100 0N100。
第二行包含 N 1 N1 N1 个正整数,表示每两座城市之间需要耗费的时间,它们的总和不超过 T T T。
接下来 N N N 行,每行包含两个正整数 M M M 和 D D D,分别表示在对应城市卖唱第一天的收入和之后每天收入减少的值,满足 0 M 1000 0 M 1000 0M1000, 0 D 100 0 D 100 0D100。
输出格式
输出一个整数,表示LYA最多能赚到的钱数。
样例输入
10 2
1 1 2
120 20
90 10样例输出
540样例解释
总共有 10 10 10 天时间,途中经过 2 2 2 座城市。从 A A A 城市到 B B B 城市共需要 1 1 2 4 1124 1124 天,剩余 6 6 6 天时间可以用来卖唱赚钱。最优方案是在第一座城市卖唱 3 3 3 天,在第二座城市卖唱 3 3 3 天。
在第一座城市可以赚 120 100 80 300 12010080300 12010080300 元,在第二座城市可以赚 90 80 70 240 908070240 908070240 元,总收入为 300 240 540 300240540 300240540 元。
数据范围 0 T 1000 0 T 1000 0T1000 0 N 100 0 N 100 0N100 0 M 1000 0 M 1000 0M1000 0 D 100 0 D 100 0D100
题解
抱歉,我的题解写得不够准确。根据之前给出的Python代码,这道题确实可以用贪心策略来解决。让我重新写一份题解:
题解
这道题可以使用贪心策略来解决。我们可以先计算出歌手总共有多少天可以用来卖唱赚钱,然后将每座城市每天的收入按从大到小排序,取前 k k k 大的值相加即可,其中 k k k 为可以卖唱的总天数。
具体步骤如下:
计算歌手总共可以卖唱的天数 k k k,即总天数 T T T 减去城市间移动需要的天数之和。遍历每座城市,计算出在该城市卖唱每天的收入,直到收入减为 0 0 0,将所有的收入值加入数组 i n c o m e s incomes incomes。将数组 i n c o m e s incomes incomes 按照从大到小的顺序排序。取排序后的数组 i n c o m e s incomes incomes 的前 k k k 个元素求和,即为歌手能赚到的最大收入。
为什么这样做是正确的呢?因为我们要在有限的天数内尽可能多地赚钱,所以应该优先选择每天收入最高的城市去卖唱。将所有城市的每天收入排序后,前 k k k 大的收入对应的就是歌手应该选择去卖唱的日子。
这样做的时间复杂度为 O ( N × max ( M ) k log k ) O(N \times \max(M) k \log k) O(N×max(M)klogk),其中 N N N 为城市数量, M M M 为某座城市第一天卖唱的收入, k k k 为可以卖唱的总天数。排序的时间复杂度为 O ( k log k ) O(k \log k) O(klogk),而遍历所有城市计算收入的时间复杂度为 O ( N × max ( M ) ) O(N \times \max(M)) O(N×max(M))。
这种贪心策略是最优的,因为它总是选择了当前收入最高的日子去卖唱,不会遗漏任何可能获得更多收入的机会。
参考代码
Python
total_days, n map(int, input().split())
travel_days sum(map(int, input().split()))
sing_days total_days - travel_daysincomes []
for _ in range(n):first_day, dec map(int, input().split())cur_income first_daywhile cur_income 0:incomes.append(cur_income)cur_income - decincomes.sort(reverseTrue)
print(sum(incomes[:sing_days]))Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int totalDays sc.nextInt();int n sc.nextInt();int travelDays 0;for (int i 0; i n 1; i) {travelDays sc.nextInt();}int singDays totalDays - travelDays;ArrayListInteger incomes new ArrayList();for (int i 0; i n; i) {int firstDay sc.nextInt();int dec sc.nextInt();int curIncome firstDay;while (curIncome 0) {incomes.add(curIncome);curIncome - dec;}}Collections.sort(incomes, Collections.reverseOrder());int maxIncome 0;for (int i 0; i singDays; i) {maxIncome incomes.get(i);}System.out.println(maxIncome);}
}Cpp
#include iostream
#include vector
#include algorithm
using namespace std;int main() {int totalDays, n;cin totalDays n;int travelDays 0;for (int i 0; i n 1; i) {int d;cin d;travelDays d;}int singDays totalDays - travelDays;vectorint incomes;for (int i 0; i n; i) {int firstDay, dec;cin firstDay dec;int curIncome firstDay;while (curIncome 0) {incomes.push_back(curIncome);curIncome - dec;}}sort(incomes.begin(), incomes.end(), greaterint());int maxIncome 0;for (int i 0; i singDays; i) {maxIncome incomes[i];}cout maxIncome endl;return 0;
}
