杭电1789贪心java实现

举报
bigsai 发表于 2021/02/03 01:24:46 2021/02/03
【摘要】 题意: 问题描述 伊格内修斯有很多功课要做。每个老师都会给他一个交作业的截止日期。如果在截止日期之后提交作业,老师会减少他的最终考试成绩。现在我们假设每个人做功课都需要一天的时间。所以希望你帮助他安排作业的次序,以尽量减少分数。 输入 输入包含多个测试用例。输入的第一行是一个整数T,即测试用例的数量。 T测试用例如下。 每个测试用例都以一个表示作业数量的正整数N(1 &lt...

题意:

问题描述
伊格内修斯有很多功课要做。每个老师都会给他一个交作业的截止日期。如果在截止日期之后提交作业,老师会减少他的最终考试成绩。现在我们假设每个人做功课都需要一天的时间。所以希望你帮助他安排作业的次序,以尽量减少分数。
输入
输入包含多个测试用例。输入的第一行是一个整数T,即测试用例的数量。 T测试用例如下。
每个测试用例都以一个表示作业数量的正整数N(1 <= N <= 1000)开始。然后是2行。第一行包含N个表示主题最后期限的整数,下一行包含N个表示分数降低的整数。
产量
对于每个测试用例,您应输出最小的总体缩减分数,每个测试用例一行。
示例输入
3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4
 
示例输出
0
3

5

分析,可在意识到这是一种贪心算法,但是要考虑贪心的策略。有按照截至日期排序和扣的分数排序。可以从扣的分数排序思考。将扣的分数从大到小排序。用数组c【】足够大表示第几天完成的内容的所值分数。有n组数据看最后一组数据分析:最后一组数据排序后为:

7 6 5 4 3 2 1

4 2 4 3 1 4 6

正常情况:

最大的那个一定要在四天前完成,他的价值最大,为了最大化利用资源就让他在第四天完成,那么c[4]=7;

第二个6 2,同理在第二天完成。

特殊情况:

第三组数据5 4.因为c[4]已经被用过,并且用过的那个数据价值一定比当前5价值高,所以可以从第四天不行,就让他的前一天完成这组数据,即c[3]=5(你可能会问遇到第三天恰好完成的怎么办,首先有两点,第一:后面第三天的分数就算没位置舍弃价值也比舍弃这个数据价值大。第二:第三天恰好完成的可以看看第二天,第一天有没有被占用,如果有空,那么就从第三天往前查找遍历,入座。如果没有空值,可以肯定前面的值都比第三天贵很多,不划算舍弃,所以当到第0个位置都没有座位,就是必须要牺牲的。)

这种方式就是最大化减小扣的分数。

代码如下:


      import java.util.Scanner;
      public class 杭电1789 {
     	public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
      int T=sc.nextInt();
      for(int TT=0;TT<T;TT++)
       {
      int num=0;
      int n=sc.nextInt();//功课数量
      int a[]=new int[n];//最后期限
      int b[]=new int[n];//降分数
      int c[]=new int[10000];
      boolean[] d=new boolean[n];
      for(int i=0;i<n;i++)
       {a[i]=sc.nextInt(); }
      for(int i=0;i<n;i++)
       {b[i]=sc.nextInt();}
      for(int i=0;i<n;i++)//按照截至日期升序
       {
      for(int j=i;j<n;j++)
       {
      if(b[i]<b[j])
       {
      int tem=a[i];
       a[i]=a[j];
       a[j]=tem;
       tem=b[i];
       b[i]=b[j];
       b[j]=tem;
       }
      if(b[j]==b[i]&&a[i]>a[j])//相同日期大的在左边,大的要先交
       {
      int tem=b[i];
       b[i]=b[j];
       b[j]=tem;
       }
       }
       }
      for(int i=0;i<n;i++)//对数据逐个处理
       {
      if(c[a[i]-1]==0) {c[a[i]-1]=b[i];}//正常情况。注意数组有c[0];对应的是第一天
      else if(c[a[i]-1]!=0)//特殊情况
       {
      for(int j=a[i]-1;j>=0;j--)
       {
      if(c[j]==0) {c[j]=b[i];break;}
      else if(j==0&&c[0]!=0) {num=num+b[i];}//在他之前没位置,在座的都比他贵,只能舍弃了
       }
       }
       }
       System.out.println(num);
       }
      	}
      }
  
 

 

 

 

 

 

 

 

 

文章来源: bigsai.blog.csdn.net,作者:Big sai,版权归原作者所有,如需转载,请联系作者。

原文链接:bigsai.blog.csdn.net/article/details/79460439

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。