博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdoj1789【贪心】
阅读量:5042 次
发布时间:2019-06-12

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

题意:

已知有n个作业,每个作业呢,都是一天可以做完,每个作业都有一个截止日期,每个作业如果超过他的截止日期会扣分,最后让你求一个怎么安排求得一个最小扣的分数。
比如现在有3个作业
截止日期:3 3 3
超过扣分:1 5 4
我们看到他们的截止日期都是3天,所以每天做一份。3天刚好做完,扣0分。
思路:
一开始一直一直瞎搞,因为听说这道题目吧。。记忆中是贪心。然后就瞎几把排序各种,按时间排,感觉非常像DP。。。但是好难DP。。然后还是贪心吧。按照花费从大到小排序,然后能处理就处理,不能处理就只能不处理了(sum+=q[ i ].t)。

#include 
using namespace std;typedef long long LL;typedef unsigned long long ULL;const double eps=1e-5;const double pi=acos(-1.0);const int mod=1e9+7;const int INF=0x3f3f3f3f;const int N=1e3+10;struct asd{ int d; int t;};asd q[N];bool vis[N];bool cmp(asd x,asd y){ if(x.t>y.t) return 1; else if(x.t==y.t){ if(x.d
>t; while(t--) { int n,i,sum,j; cin>>n; for(i=1;i<=n;i++){ scanf("%d",&q[i].d); } for(i=1;i<=n;i++){ scanf("%d",&q[i].t); } sort(q+1,q+n+1,cmp); memset(vis,0,sizeof(vis)); sum=0; for(i=1;i<=n;i++){ for(j=q[i].d;j>=1;j--){ if(!vis[j]){ vis[j]=1; break; } } if(j==0) sum+=q[i].t; } cout<
<

转载于:https://www.cnblogs.com/keyboarder-zsq/p/5934439.html

你可能感兴趣的文章
iOS设计模式 - 中介者
查看>>
centos jdk 下载
查看>>
HDU 1028 Ignatius and the Princess III(母函数)
查看>>
(转)面向对象最核心的机制——动态绑定(多态)
查看>>
token简单的使用流程。
查看>>
django创建项目流程
查看>>
UIActionSheet 修改字体颜色
查看>>
Vue 框架-01- 入门篇 图文教程
查看>>
Spring注解之@Lazy注解,源码分析和总结
查看>>
多变量微积分笔记24——空间线积分
查看>>
Magento CE使用Redis的配置过程
查看>>
poi操作oracle数据库导出excel文件
查看>>
(转)Intent的基本使用方法总结
查看>>
Mac 下的Chrome 按什么快捷键调出页面调试工具
查看>>
Windows Phone开发(24):启动器与选择器之发送短信
查看>>
JS截取字符串常用方法
查看>>
Google非官方的Text To Speech和Speech Recognition的API
查看>>
stdext - A C++ STL Extensions Libary
查看>>
Django 内建 中间件组件
查看>>
bootstrap-Table服务端分页,获取到的数据怎么再页面的表格里显示
查看>>