\(设x_{i}为第i个同学从第i-1个同学获得的糖果数，若x_{i} < 0，则第i-1个同学从第i个同学获得-x_{i}个糖果\)
\(特别地，x_{1}为第1个同学从第n个同学获得的糖果数\)
$latex 均分后，每个同学拥有的糖果为avg[……]
标签：贪心
[LOJ10009]钓鱼
\(枚举每一个湖k作为终止点，期间的钓鱼次数则为\frac{60H+5\sum_{i=1}^{k-1} T_{i}}{5}\)
\(要使钓到数量最多，则需要保证每一次钓到的鱼最多，用优先队列维护\)
$latex 要注意\frac{60H+5\sum_{[……]
[LOJ10008]家庭作业
和[LOJ10004]智力大冲浪一样的思路
\(但注意的LOJ10004中复杂度为O(Nt)，肯定会TLE，所以要考虑优化\)
\(注意到每次查找空闲时间的时候都是从t_{i}往前找，复杂度为O(t)\)
$latex 可以用并查集维护每段连续的被[……]
[LOJ10007]线段
和[LOJ10000]活动安排一样的思路
|
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 |
#include<stdio.h> #include<algorithm> using namespace std; struct Line { int a, b; bool operator < (const Line &A) const { return b < A.b; } } l[1000010]; int n, p, k; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d%d", &l[i].a, &l[i].b); sort(l+1, l+n+1); for (int i = 1; i <= n; ++i) { if (l[i].a >= p) { p = l[i].b; k++; } } printf("%d", k); return 0; } |
[LOJ10006]数列分段
这道算贪心吗……可以说是模拟了
从前往后扫就行了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include<stdio.h> int n, m, cnt; int main() { scanf("%d%d", &n, &m); for (int i = 1, x, xs = 0; i <= n; ++i) { scanf("%d", &x); if (xs+x > m) { xs = 0; cnt++; } xs += x; } printf("%d", cnt+1); return 0; } |
[LOJ10005]数列极差
\(根据贪心的策略，取max的时候尽量保证数列中两个最小的数相乘，取min反之\)
\(用优先队列维护数列，复杂度O(nlogn)\)
|
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 |
#include<stdio.h> #include<algorithm> #include<queue> using namespace std; priority_queue<int> a; priority_queue<int, vector<int>, greater<int> > b; int n; int main() { scanf("%d", &n); for (int i = 1, x; i <= n; ++i) { scanf("%d", &x); a.push(x); b.push(x); } while(a.size() > 1) { int x = a.top(); a.pop(); int y = a.top(); a.pop(); a.push(x*y+1); x = b.top(); b.pop(); y = b.top(); b.pop(); b.push(x*y+1); } printf("%d", b.top()-a.top()); return 0; } |
[LOJ10004]智力大冲浪
\(根据贪心的原则，罚款尽可能小，也就是说罚款大的要尽可能保证能不罚，所以将w从大到小排序\)
\(对于w_{i}，从t_{i}往前安排，这样t_{i}前的任务也能充分完成，时间复杂度O(n^{2})\)
[crayon-61a744e48108b[……]
[LOJ10003]加工生产调度
\(记所有产品的集合为N = \{1, 2, …, n\}, S \subseteq N\)
\(记T(S, t)为等待B机器t时间后完成S的所需最短时间，则有\)
$$ T(S, t) = \min_{i \in S}\{A_{i}+T(S-\{i\[……]
[LOJ10002]喷水装置
对于一个喷头，能完整覆盖的区域只有 \(l ~ r\) 所以只需要把圆形变成长为 \(r-l\) ，宽为 \(\frac{W}{2}\) 的长方形就行了
对 \(l\) 进行排序，选取最大的 \(r\) 就足够了
注意：[……]
[LOJ10001]种树
对于 \(h\) 组建议，按其\(e\)由小到大排序
对于一个建议，先从前往后数是否满足\(t\)棵树，不满足则从后往前补种
复杂度\(O(n)\)
|
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 |
#include<stdio.h> #include<algorithm> using namespace std; struct Quest { int b, e, t; bool operator < (const Quest &A) const { return e < A.e; } } q[5010]; int n, h, a[30010], tot; int main() { scanf("%d%d", &n, &h); for (int i = 1; i <= h; ++i) scanf("%d%d%d", &q[i].b, &q[i].e, &q[i].t); sort(q+1, q+h+1); for (int i = 1, k; i <= h; ++i) { k = 0; for (int j = q[i].b; j <= q[i].e; ++j) { if (a[j]) k++; if (k == q[i].t) break; } if (k < q[i].t) { for (int j = q[i].e; j >= q[i].b; --j) { if (!a[j]) { a[j] = 1; k++; tot++; if (k == q[i].t) break; } } } } printf("%d", tot); return 0; } |
&nbs[……]