题意:有n门考试,对于考试i,不复习它能考si分,复习它的每小时能提高ai分,每过一小时ai会减小di,也就是说,连续复习某门科目每小时提高的分为ai, ai-di, ai-2di...,但每门考试最高分不超过100分,给定每门考试的考试时间,且考试本身不占时间,合理安排复习计划,问能否让所有考试都不低于60分,如果可以,总和最大为多少。

思路:比较明显的贪心,但难以想到正确的贪心策略。我们把问题分成两步,所有考试全部通过60分和得分总和最大。对于第一步,对于不复习分数低于60分的科目,先复习一段时间让它分数达到60分,贪心从考试时间往前延伸找空闲时间复习(一旦找不到空闲时间,则无解了)。对于第二步,按时间顺序的逆序处理,对于某个时间t,枚举所有考试时间大于等于t的科目,找到某一科目,使得复习它提高的分数最高,那么时间t就用来复习这门功课。

 #pragma comment(linker, "/STACK:10240000,10240000")

 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <ctime>
#include <cctype>
#include <set>
#include <bitset>
#include <functional>
#include <numeric>
#include <stdexcept>
#include <utility> using namespace std; #define mem0(a) memset(a, 0, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define define_m int m = (l + r) >> 1
#define rep_up0(a, b) for (int a = 0; a < (b); a++)
#define rep_up1(a, b) for (int a = 1; a <= (b); a++)
#define rep_down0(a, b) for (int a = b - 1; a >= 0; a--)
#define rep_down1(a, b) for (int a = b; a > 0; a--)
#define all(a) (a).begin(), (a).end()
#define lowbit(x) ((x) & (-(x)))
#define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {}
#define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
#define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}
#define pchr(a) putchar(a)
#define pstr(a) printf("%s", a)
#define sstr(a) scanf("%s", a)
#define sint(a) scanf("%d", &a)
#define sint2(a, b) scanf("%d%d", &a, &b)
#define sint3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define pint(a) printf("%d\n", a)
#define test_print1(a) cout << "var1 = " << a << endl
#define test_print2(a, b) cout << "var1 = " << a << ", var2 = " << b << endl
#define test_print3(a, b, c) cout << "var1 = " << a << ", var2 = " << b << ", var3 = " << c << endl typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi; const int dx[] = {, , -, , , , -, -};
const int dy[] = {-, , , , , -, , - };
const int maxn = 3e4 + ;
const int md = ;
const int inf = 1e9 + ;
const LL inf_L = 1e18 + ;
const double pi = acos(-1.0);
const double eps = 1e-; template<class T>T gcd(T a, T b){return b==?a:gcd(b,a%b);}
template<class T>bool max_update(T &a,const T &b){if(b>a){a = b; return true;}return false;}
template<class T>bool min_update(T &a,const T &b){if(b<a){a = b; return true;}return false;}
template<class T>T condition(bool f, T a, T b){return f?a:b;}
template<class T>void copy_arr(T a[], T b[], int n){rep_up0(i,n)a[i]=b[i];}
int make_id(int x, int y, int n) { return x * n + y; } struct Node {
int r, s, a, d;
Node(int r = , int s = , int a = , int d = ): r(r), s(s), a(a), d(d) {}
bool operator < (const Node that) const {
return r < that.r;
}
};
Node node[];
bool occ[]; int main() {
//freopen("in.txt", "r", stdin);
int n;
while (cin >> n) {
int maxt = ;
bool ok = true;
mem0(occ);
rep_up0(i, n) {
int s, t, a, d, tmp = ;
cin >> s >> t >> a >> d;
node[i] = Node(t, s, a, d);
max_update(maxt, t);
}
sort(node, node + n);
rep_up0(i, n) {
int cur = node[i].r;
while (node[i].s < ) {
while (occ[cur] && cur) cur--;
if (!cur || node[i].a <= ) {
ok = false;
break;
}
occ[cur] = true;
node[i].s += node[i].a;
node[i].a -= node[i].d;
}
if (!ok) break;
}
rep_down1(i, maxt) {
if (!occ[i]) {
int s = , p;
rep_up0(j, n) {
if (node[j].r >= i) {
int dat = node[j].a;
if (node[j].s + dat > ) dat = - node[j].s;
if (dat > s) {
s = dat;
p = j;
}
}
}
if (s) {
node[p].s += s;
node[p].a -= node[p].d;
}
}
}
int ans = ;
rep_up0(i, n) {
ans += node[i].s;
}
if (ok) cout << ans << endl;
else puts("you are unlucky");
}
}

最新文章

  1. Codeforces Round #377 (Div. 2) B. Cormen — The Best Friend Of a Man(贪心)
  2. 如何将数据库中的表导入到PowerDesigner中
  3. POJ2184 Cow Exhibition[DP 状态负值]
  4. 使用var声明的变量 和 直接赋值并未声明的变量的区别
  5. Starling性能优化技巧十五则
  6. DataTable.ImportRow()与DataTable.Rows.Add()的区别
  7. Query语句对系统性能的影响
  8. Linux学习第一步(虚拟机的和镜像文件的安装)
  9. R读取excel文件乱码 read.xlsx() 解决方法
  10. 安卓服务Service详解
  11. mysql ssh 跳板机(堡垒机???)连接服务器
  12. 【转载】IIS出现“HTTP 错误 500.0,C:\php\php-cgi.exe - FastCGI 进程意外退出”解决方法
  13. 【UOJ#275】组合数问题(卢卡斯定理,动态规划)
  14. npm错误:Error: listen EADDRNOTAVAIL
  15. python threading
  16. 利用神经网络进行网络流量识别——特征提取的方法是(1)直接原始报文提取前24字节,24个报文组成596像素图像CNN识别;或者直接去掉header后payload的前1024字节(2)传输报文的大小分布特征;也有加入时序结合LSTM后的CNN综合模型
  17. C++函数的传值调用&amp;指针调用&amp;引用调用
  18. SDN期末作业博客
  19. InstallShield卸载不彻底,残留大量dll文件
  20. sass安装及使用

热门文章

  1. C#开发BIMFACE系列31 服务端API之模型对比2:获取模型对比状态
  2. 【题解】P3349 [ZJOI2016]小星星 - 子集dp - 容斥
  3. 数值计算方法实验之Newton 多项式插值(MATLAB代码)
  4. python os模块判断文件是否存在
  5. 苹果登录服务端JWT算法验证-PHP
  6. testlink配置修改
  7. 线上Bug无法复现怎么办?老司机教你一招,SpringBoot远程调试不用愁!
  8. Makefile 中引用多个 include 路径
  9. 一篇文章带你编写10种语言HelloWorld
  10. java中ThreadPool的介绍和使用