当前位置：网站首页>nyoj757 期末考试（优先队列）

nyoj757 期末考试（优先队列）

2022-08-05 11:03:00 【51CTO】

期末考试

1000 ms | 内存限制： 65535

马上就要考试了，小T有许多作业要做，而且每个老师都给出来了作业要交的期限，如果在规定的期限内没

交作业就会扣期末成绩的分数，假设完成每门功课需要一天的时间，你能帮助小T扣除的分数最小吗？

输入n，表示n门功课(n<2000)，接下来n行，每行两个数a，b，分别表示交作业的最后期限，迟交扣除的分数。

(以文件结尾)

输出输出扣除的最小分数。样例输入

3 3 10 3 5 3 1 3 1 6 3 2 1 3 7 1 3 4 2 6 1 4 7 2 6 4 5 3 4

样例输出

0 3 5

记得以前做过类似的就直接敲了

       
       #include <stdio.h>
       
       #include <algorithm>
       
       #include <queue>
       
       using 
       
       namespace 
       
       std;
       
       struct 
       
       node 
       
{
       
       int 
       
       day,
       
       cost;
       
}
       
       c[
       
       2005];
       
       bool 
       
       cmp(
       
       node 
       
       x,
       
       node 
       
       y)
       
{
       
       if(
       
       x.
       
       day
       
       <
       
       y.
       
       day) 
       
       return 
       
       true;
       
       if(
       
       x.
       
       day
       
       ==
       
       y.
       
       day
       
       &&
       
       x.
       
       cost
       
       <
       
       y.
       
       cost) 
       
       return 
       
       true;
       
       return 
       
       false;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       n,
       
       sum;
       
       priority_queue
       
       <
       
       int,
       
       vector
       
       <
       
       int
       
       >,
       
       greater
       
       <
       
       int
       
       > 
       
       >
       
       s;
       
       while(
       
       scanf(
       
       "%d",
       
       &
       
       n)
       
       !=
       
       EOF)
       
  {
       
       while(
       
       !
       
       s.
       
       empty())
       
       s.
       
       pop();
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++)
       
       scanf(
       
       "%d %d",
       
       &
       
       c[
       
       i].
       
       day,
       
       &
       
       c[
       
       i].
       
       cost);
       
       sort(
       
       c,
       
       c
       
       +
       
       n,
       
       cmp);
       
       sum
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++)
       
    {
       
       if(
       
       s.
       
       size()
       
       <
       
       c[
       
       i].
       
       day)
       
       //s.size()可以理解为天数。如果当前天数小于最后完成的天数，证明还是有天数空间的，直接入队列
       
       s.
       
       push(
       
       c[
       
       i].
       
       cost);
       
       else
       
       //如果当前天数大于最后完成的天数，必须要扣除分数了，为了使得扣除的分数最小，比较s.top()和当前的c[i].cost，舍弃扣除的最小的
       
      {
       
       int 
       
       x
       
       =
       
       s.
       
       top();
       
       if(
       
       x
       
       <
       
       c[
       
       i].
       
       cost)
       
       s.
       
       pop(),
       
       s.
       
       push(
       
       c[
       
       i].
       
       cost),
       
       sum
       
       +=
       
       x;
       
       else
       
       sum
       
       +=
       
       c[
       
       i].
       
       cost;
       
      }
       
    }
       
       printf(
       
       "%d\n",
       
       sum);
       
  }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.