P1475智力大冲浪，详细的解题思路

大家好，我是讯享网，很高兴认识大家。

题目描述

解题思路

这题难其实难在读不懂题目到底想要表达一个什么意思，或者说误解了题目的意思，如果读懂了题目，明白了题目想要我们解决一个什么样的问题，那么这题将会变得非常简单，那么题目到底什么意思呢？

题目的意思：

题目给了我们n个时间段，从第一个时间段一直到第n个时间段，有n个小游戏，每个小游戏需要在规定期限ti前完成，也就是说如过某一个小游戏的期限是4那么其需要在第4个时间段之前完成这个小游戏否则就要罚款，而每一个小游戏都可以在一个时间段内完成，也就是说，在题目所划分的这n个时间段内我们都可以完成一个小游戏，就是说如果一个小游戏的期限是4那么我们可以让它在第一个时间段完成，也可以让他在第二个时间段完成，也可以让它在第三个时间段完成，也可以在第四个时间段完成，这些时间段都在规定期限内，所以只要在这些时间段完成了该游戏就不会被罚款，所以这题的目的就是为了让我们安排做游戏的顺序，即如何安排游戏顺序才能让罚数最小？我们很容易可以想到，要让罚款数多的小游戏尽量在规定时间内完成，还要完成尽可能多的小游戏，所以对于一个时间限制为ti的小游戏而言我们应该把它放在其最后限定期限完成，这样就可以减少对其它小游戏时间的挤占，能尽可能多的完成更多的小游戏。于是我们需要一个数组lim_t来存放每一个小游戏的期限，还要一个数组fine来存放没在规定期限内完成小游戏将会被扣除的罚款，还需要一个数组is_free来判断当前时间段是否空闲，如果空闲则代表当前时间段没有被其它小游戏挤占，那么就可以用来玩游戏。将数组按照罚款的大小进行排序，让罚款多的游戏尽量在限期内完成，让该游戏在限期的最后一个时间段完成，减少对其它游戏时间的挤占，完成尽可能多的小游戏。算法实现源代码以及运行结果截图如下：

算法源代码：

//智力大冲浪 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #define N 500 int main() { int m; //表示节目组最初所给出的奖励 int n; //表示有n个小游戏 int lim_t[N]; //每个小游戏规定的时限 int fine[N]; //未在规定时限内完成该小游戏的惩罚 int is_free[N]; while (scanf("%d%d", &m, &n) != EOF) { for (int i = 0; i < n; i++) { is_free[i] = 0; scanf("%d", &lim_t[i]); //每一个小游戏的时限 } for (int i = 0; i < n; i++) { scanf("%d", &fine[i]); //若不能在规定的时间内完成该小游戏时所需要扣除的罚款 } for (int i = 0; i < n - 2; i++) //将两个数组按照罚款数进行从大到小排序 { for (int j = 0; j < n - 2 - i; j++) { if (fine[j]<fine[j+1]) { int temp; temp = lim_t[j]; lim_t[j] = lim_t[j + 1]; lim_t[j + 1] = temp; temp = fine[j]; fine[j] = fine[j + 1]; fine[j + 1] = temp; } } } for (int i = 0; i < n; i++) { for (int j = lim_t[i]; j >= 1; j--) { if (is_free[j] == 0) { is_free[j] = 1; break; } if (j == 1) { m = m - fine[i]; //如果在限期之前的每一个时间段都已经被其它小游戏挤占了，那么就没有时间来完成该小游戏，该小游戏就不能在限定期限内完成，那么就要罚款 } } } printf("%d\n", m); } return 0; }

讯享网

运行结果截图：

这里分享一下一个小技巧吧：对于一个很难很难的算法题目，当我们不会做的时候都会想到去网上搜别人的解题方法，学习一下，但是很有可能会存在读不懂别人的方法的情况，因为每一个人对于同一个题目所困惑的点不一样，写这道题解的人只会写出他在做这道题时觉得困惑的地方，给出该困惑的解释，但是有可能你的困惑点和他不一样，那么他的这篇文章就不能解决你的困惑，所以一个可行的办法是，将别人正确的代码调试一遍，观察在调试的过程中，各个变量的变化情况，这样就会帮助你更进一步的理解写该博客的作者的解题思路，也能让你对该题的解法有一个更深刻的理解。

P1475智力大冲浪，详细的解题思路

题目描述

解题思路

相关推荐