HDU - 1789 Doing Homework again（贪心） ~~~学了一波sort对结构体排序-白红宇的个人博客

HDU - 1789 Doing Homework again（贪心） ~~~学了一波sort对结构体排序

发布日期：2021-05-13 00:44:51 浏览次数：14 分类：博客文章

本文共 1413 字，大约阅读时间需要 4 分钟。

　　题目中因为天数和分数是对应的，所以我们使用一个结构体来存分数和截止如期。

　　一开始做这道题的时候，很自然的就想到对天数排序，然后天数一样的分数从大到小排序，最后WA了之后才发现没有做到“舍小取大”的贪心。所以改变一下策略，对分数排序，如果分数一样的话，时间从小到大排序（因为我们的目的就是先做分多的作业，所以分数一样的得放到前几天去做）。

　　（具体sort排结构体知识见代码里面，其实也可以写两次for来排序）；

　　思路：排好序之后，从小到大遍历，每找到一个分数，去寻找对应的天数到第一天中有没有空余的天数（因为要先做分多的），实现寻找空余天数就是从那一天往第一天遍历（（（①））），遍历啥子？？？当然定义一个标记数组来记录你哪一天用来做作业了。如果有空余天就让他在那一天过，如果没有空余天，就是完不成的了，累计加起来，最后输出结果即可。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 using namespace std;10 11 struct ss {12 int time, p;13 }t[1010];14 15 int cmp (const ss a, const ss b) {16 // if (a.p>b.p) {17 // return 1;18 // } else if (a.p==b.p&&a.time
            
              b.p;28 } else {29 return a.time < b.time;30 }31 }32 33 bool used[1010];34 35 int main() {36 int T, num;37 cin >> T;38 while (T--) {39 int res = 0;40 cin >> num;41 for (int i = 0; i < num; ++i) {42 scanf ("%d", &t[i].time);43 }44 for (int i = 0; i < num; ++i) {45 scanf ("%d", &t[i].p);46 }47 sort (t, t+num, cmp);48 memset (used, false, sizeof(used));49 50 int j;51 for (int i = 0; i < num; ++i) {52 for (j = t[i].time; j > 0; --j) {53 if (!used[j]) {54 used[j] = true;55 break;56 }57 }58 if (j == 0) {59 res += t[i].p;60 }61 }62 cout << res << endl;63 }64 return 0;65 }

View Code

思考：①处为什么不可以从第一天遍历？

答：如果从第一天遍历的话，那么很可能把只有一天的交作业时间的科目占用了，后面有空余的天，也是达不到扣最少分的结果的。

上一篇：HDU - 3347 Calculate the expression — 模拟 + map存变量

下一篇：hdu 2072 1106学一波字符串分割，C语言与C++两种方法

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章