太傅博客 - 贪心
type: channel
link: https://acm.taifua.com/tag/greedy/
items: LeetCode435. Non-overlapping Intervals（贪心 / 动态规划）
items: LeetCode455. Assign Cookies（贪心）
items: 牛客多校 2018 第二场 D Money（贪心/DP）
items: CSU2026 Daydreaming Stockbroker（贪心）
items: HDU6438 Buy and Resell（贪心+优先队列/multiset）
items: Codeforces Round #437 (Div. 1)D Buy Low Sell High（贪心+优先队列/multiset）
items: Educational Codeforces Round 44 (Div. 2)（模拟+贪心）
items: Gym 100803C Shopping（贪心）

LeetCode435. Non-overlapping Intervals（贪心 / 动态规划）
type: item
date: 2019-04-11T12:11:00+08:00
description: LeetCode435. Non-overlapping Intervals（贪心 / 动态规划）MediumAccepted：36,286Submissions：87,349Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.Note:You may assume the interval's end point is always bigger than its start point.Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.Example 1:Input: [ [1,2], [2,3], [3,4], [1,3] ] Output: 1 Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.Example 2:Input: [ [1,2], [1,2], [1,2] ] Output: 2 Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.Example 3:Input: [ [1,2], [2,3] ] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.链接https://leetcode.com/problems/non-overlapping-intervals题意给定一些区间的集合，问你要删除的最少区间的数量使得剩余的区间不重叠。保证区间的结束点大于起始点以及边界值相同不算重叠。题解求删除的最少区间数量可以转化为求集合中不重叠的区间最多有多少个。为了方便判断重叠，我们可以对区间进行排序。按照起始点从小到大排序，起始点相同时按终止点从小到大排序。这样我们就将问题转变成了类“最长上升子序列”，区间化点，对于当前区间，如果它的左端点大于等于前面的右端点那么就加1。此外，还可以使用“贪心”来做，同样先对区间进行排序，但是按照终止点从小到大排序，每次选择终止点最小的，这样就可以给后面的区间留出更多的空间，从而选择更多不重叠的空间。贪心时间复杂度：$O(n)$，动态规划时间复杂度：$O(n^2)$。代码Runtime: 12 ms, faster than 86.40% of C++ online submissions for Non-overlapping Intervals.Memory Usage: 9.8 MB, less than 73.08% of C++ online submissions for Non-overlapping Intervals.bool cmp(const Interval & a, const Interval & b) { if (a.end != b.end) return a.end < b.end; return a.start < b.start; } class Solution { public: int eraseOverlapIntervals(vector<Interval>& intervals) { int n = intervals.size(); if (n == 0) return 0; sort(intervals.begin(), intervals.end(), cmp); int pre = 0, ans = 1; for (int i = 1; i < n; ++i) { if (intervals[i].start >= intervals[pre].end) { ++ans; pre = i; } } return n - ans; } };Runtime: 396 ms, faster than 5.18% of C++ online submissions for Non-overlapping Intervals.Memory Usage: 9.9 MB, less than 15.38% of C++ online submissions for Non-overlapping Inte…

LeetCode455. Assign Cookies（贪心）
type: item
date: 2019-04-11T10:06:00+08:00
description: LeetCode455. Assign Cookies（贪心）EasyAccepted：60,685Submissions：125,878Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.Note:You may assume the greed factor is always positive. You cannot assign more than one cookie to one child.Example 1:Input: [1,2,3], [1,1] Output: 1 Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.Example 2:Input: [1,2], [1,2,3] Output: 2 Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. You have 3 cookies and their sizes are big enough to gratify all of the children, You need to output 2.链接https://leetcode.com/problems/assign-cookies题意假设你现在要给你的孩子们分一些饼干，每个孩子最多分一个。每个孩子都有一个贪婪指数gi，每块饼干有一个尺寸si，当si大于等于gi时，就可以把饼干分给孩子，孩子就会变得开心，问如何分配饼干让最多的孩子开心，输出最多孩子开心的数量。题解此时，一个表情包在我脑海中浮现，“懂不懂，这道题用贪心”。我们要使得尽可能多的孩子开心，就是尽可能分配更多的饼干。考虑一个贪心策略：每次尽可能的先分配最大尺寸的饼干给贪婪指数最大的孩子，这样我们就可以获得一个最优解。为了更好处理，我们可以对孩子的贪婪指数和饼干的尺寸从大到小排序，然后使用一个while循环。因为要排序，所以时间复杂度为$O(nlogn)$，一个比较“暴力”的写法是两重循环。代码Runtime: 44 ms, faster than 74.03% of C++ online submissions for Assign Cookies.Memory Usage: 10.4 MB, less than 76.00% of C++ online submissions for Assign Cookies.class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { int n = g.size(), m = s.size(); sort(g.begin(), g.end(), greater <>()); // 从大到小排序 sort(s.begin(), s.end(), greater <>()); int ans = 0; int i = 0, j = 0; while (i < n && j < m) { if (s[j] >= g[i]) { ++i, ++j; ++ans; } else ++i; } return ans;…

牛客多校 2018 第二场 D Money（贪心/DP）
type: item
date: 2018-08-27T16:46:00+08:00
description: Money时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld题目描述White Cloud has built n stores numbered from 1 to n.White Rabbit wants to visit these stores in the order from 1 to n.The store numbered i has a price a[i] representing that White Rabbit can spend a[i] dollars to buy a product or sell a product to get a[i] dollars when it is in the i-th store.The product is too heavy so that White Rabbit can only take one product at the same time.White Rabbit wants to know the maximum profit after visiting all stores.Also, White Rabbit wants to know the minimum number of transactions while geting the maximum profit.Notice that White Rabbit has infinite money initially.输入描述:The first line contains an integer T(0<T<=5), denoting the number of test cases.In each test case, there is one integer n(0<n<=100000) in the first line,denoting the number of stores.For the next line, There are n integers in range [0,2147483648), denoting a[1..n].输出描述:For each test case, print a single line containing 2 integers, denoting the maximum profit and the minimum number of transactions.输入1 5 9 10 7 6 8输出3 4链接https://www.nowcoder.com/acm/contest/140/D题意有n个商店，R可以在第i个商店花p[i]元买一件商品或者以p[i]元卖出一件商品，R在同一时刻最多只能拥有一件商品，问R经过n个商店后能获取的最大收益，并且要求交易次数最少。题解低买高卖问题，限制了同时最多只能拥有一件商品。当前商品要是比下一件商品价格更低，那么当前买入下次卖出，不过后面可能会有价格更高的情况出现，其实还是一样的。A B C (A<B<C)，A买入B卖出B买入C卖出就等价于A买入C卖出，至于交易次数最少，只需要记录连续上升区间数量。、详细的题解可以参考博客：传送门。思路：1、贪心。后面的商品比前面的贵的话，一定要买前面的，卖后面的。2、在价格曲线上的连续递增的一段上，在开头买，在末尾卖肯定是最优的（利润最多，同时交易次数最少），中间多几次操作，利润是相同的3、最多的利润，即每条递增段的头尾相减之和4、利润最多的交易次数即连续递增段数量标准题解首先，如果a[i]=a[i+1]，则可以删掉第i+1个商店。因为任何在第i+1个商店进行的交易都可以转为在第i个商店进行，且收益不变。之后，如果a[i]<a[i+1]，则离开第i个商店时一定要带上一件商品。如果a[i]>a[i+1]，则离开第i个商店时一定要空着手。这样，第一问的答案max(a[i+1]-a[i],0)的累加，第二问的答案就为长度>1的极大递增连续段的数量。标准题解中还有DP思路，f[i][0/1]表示已经访问完了i个商店，你手中是否有商品，此时的最大收益。g[i][0/1]表示当f[i][j]取最大值时最少的交易次数。代码答案正确 89ms, 1252kb, length: 758#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int maxn = 100010; ll a[m…

CSU2026 Daydreaming Stockbroker（贪心）
type: item
date: 2018-08-27T14:28:00+08:00
description: Daydreaming StockbrokerTime Limit: 1 SecMemory Limit: 512 MbSubmitted: 67Solved: 20DescriptionGina Reed, the famous stockbroker, is having a slow day at work, and between rounds of solitaire she is daydreaming. Foretelling the future is hard, but imagine if you could just go back in time and use your knowledge of stock price history in order to maximize your profits!Now Gina starts to wonder: if she were to go back in time a few days and bring a measly $100 with her, how much money could she make by just buying and selling stock in Rollercoaster Inc. (the most volatile stock in existence) at the right times? Would she earn enough to retire comfortably in a mansion on Tenerife?Note that Gina can not buy fractional shares, she must buy whole shares in Rollercoaster Inc. The total number of shares in Rollercoaster Inc. is 100 000, so Gina can not own more than 100 000 shares at any time. In Gina’s daydream, the world is nice and simple: there are no fees for buying and selling stocks, stock prices change only once per day, and her trading does not influence the valuation of the stock.InputThe first line of input contains an integer d (1 ≤ d ≤ 365), the number of days that Gina goes back in time in her daydream. Then follow d lines, the i’th of which contains an integer pi (1 ≤ pi ≤ 500) giving the price at which Gina can buy or sell stock in Rollercoaster Inc. on day i. Days are ordered from oldest to newest.OutputOutput the maximum possible amount of money Gina can have on the last day. Note that the answer may exceed $2^{32}$.Sample Input6 100 200 100 150 125 300Sample Output650链接http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2026题意给你接下来n天的股票价格，每天可以买入或者卖出多股，问n天之后最大的收益（包括最开始的钱），假设最开始有100元。题解没有了交易只能为1份的“限制”，不过还是低价买入高价卖出的贪心做法。遍历找到一个连续的最低价格买入，遇到高价就卖出，但是后面可能会有更高的价格卖出，所以需要记录上一次交易的价格和数量，到一个更高的价格再次交易，相当于上次没有交易。100 200 300 ，(200 - 100) * num + (300 -200) * num = (300-200+200-100) * num。代码StatusAcceptedMemory2024kBLength640// money当前拥有总价值，curprice记录当前交易价格，number记录可购买的升值股数 …

HDU6438 Buy and Resell（贪心+优先队列/multiset）
type: item
date: 2018-08-27T11:01:00+08:00
description: Buy and ResellTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1469Accepted Submission(s): 488Problem DescriptionThe Power Cube is used as a stash of Exotic Power. There are n cities numbered 1,2,…,n where allowed to trade it. The trading price of the Power Cube in the i-th city is ai dollars per cube. Noswal is a foxy businessman and wants to quietly make a fortune by buying and reselling Power Cubes. To avoid being discovered by the police, Noswal will go to the i-th city and choose exactly one of the following three options on the i-th day:spend ai dollars to buy a Power Cuberesell a Power Cube and get ai dollars if he has at least one Power Cubedo nothingObviously, Noswal can own more than one Power Cubes at the same time. After going to the n cities, he will go back home and stay away from the cops. He wants to know the maximum profit he can earn. In the meanwhile, to lower the risks, he wants to minimize the times of trading (include buy and sell) to get the maximum profit. Noswal is a foxy and successful businessman so you can assume that he has infinity money at the beginning.InputThere are multiple test cases. The first line of input contains a positive integer T (T≤250), indicating the number of test cases. For each test case:The first line has an integer n. ($1≤n≤10^5$)The second line has n integers a1,a2,…,an where ai means the trading price (buy or sell) of the Power Cube in the i-th city. ($1≤a_i≤10^9$)It is guaranteed that the sum of all n is no more than $5×10^5$.OutputFor each case, print one line with two integers —— the maximum profit and the minimum times of trading to get the maximum profit.Sample Input3 4 1 2 10 9 5 9 5 9 10 5 2 2 1Sample Output16 4 5 2 0 0HintIn the first case, he will buy in 1, 2 and resell in 3, 4. profit = - 1 - 2 + 10 + 9 = 16 In the second case, he will buy in 2 and resell in 4. profit = - 5 + 10 = 5 In the third case, he will do nothing and earn nothing. profit = 0Source…

Codeforces Round #437 (Div. 1)D Buy Low Sell High（贪心+优先队列/multiset）
type: item
date: 2018-08-27T00:53:00+08:00
description: Buy Low Sell Hightime limit per test: 2 secondsmemory limit per test: 256 megabytesYou can perfectly predict the price of a certain stock for the next N days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. Initially you own zero shares, and you cannot sell shares when you don't own any. At the end of the N days you would like to again own zero shares, but want to have as much money as possible.InputInput begins with an integer N ($2 ≤ N ≤ 3·10^5$), the number of days.Following this is a line with exactly N integers $p_1, p_2, ..., p_N(1 ≤ p_i ≤ 10^6)$. The price of one share of stock on the i-th day is given by $p_i$.OutputPrint the maximum amount of money you can end up with at the end of N days.Examplesinput9 10 5 4 7 9 12 6 2 10output20input20 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4output41NoteIn the first example, buy a share at 5, buy another at 4, sell one at 9 and another at 12. Then buy at 2 and sell at 10. The total profit is - 5 - 4 + 9 + 12 - 2 + 10 = 20.链接http://codeforces.com/contest/866/problem/D题意给定n个数字表示接下来n天的的股价，每天可以选择买一份股票，卖一份股票或者什么都不做，最开始拥有零份股票，有足够多的钱，问n天之后能获得的最大收益。题解思考一个问题，怎么才能获得收益？当然是低价买入高价卖出，但是问题是如果现在就卖出了后面可能会有更高的价格可以卖出。怎么解决这个问题呢？我们可以用一个优先队列（从小到大排序）代表当前所持有的所有股票，枚举每个时候的股票价格，如果队首元素值小于当前枚举值，那么就可以卖出股票赚取利润，队首元素出队，但是注意需要把当前枚举值再次加入队列，因为被弹出的队首元素可能会和后面价格更高股票交易获取更多的利润，可以用当前枚举值与后面价格更高的股票交易，相当于当前枚举的股票没有进行操作。A买入B卖出，B买入C卖出等价于A买入C卖出，相当于B没有操作。比如2 5 9，5-2=3+9-5=4= 9+5-(5-2)=7。具体参见代码，有两种写法，升序优先队列priority_queue <ll, vector <ll>, greater <ll> > Q;和可重复集合multiset <ll> S。写法一Accepted 140 ms 6200 KB#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> #include <algorithm> typedef long long ll; using namespace std; int main() { int n; ll x, ans = 0; priority_queue <ll, vector <ll>, greater <ll> > Q; // scanf("%d", &n); cin >> n; for (int i = 0; i < n; ++i) { scanf("%lld", &x); Q.push(x); if (Q.top() < x) { …

Educational Codeforces Round 44 (Div. 2)（模拟+贪心）
type: item
date: 2018-05-25T11:23:00+08:00
description: A. Chess Placing（模拟）time limit per test：1 secondmemory limit per test：256 megabytesYou are given a chessboard of size 1 × n. It is guaranteed that n is even. The chessboard is painted like this: "BWBW...BW".Some cells of the board are occupied by the chess pieces. Each cell contains no more than one chess piece. It is known that the total number of pieces equals to $\frac{n}{2}$.In one step you can move one of the pieces one cell to the left or to the right. You cannot move pieces beyond the borders of the board. You also cannot move pieces to the cells that are already occupied.Your task is to place all the pieces in the cells of the same color using the minimum number of moves (all the pieces must occupy only the black cells or only the white cells after all the moves are made).InputThe first line of the input contains one integer n (2 ≤ n ≤ 100, n is even) — the size of the chessboard.The second line of the input contains $\frac{n}{2}$ integer numbers $p_1, p_2, …, p_{\frac{n}{2}}$ ($1 ≤ p_i ≤ n$) — initial positions of the pieces. It is guaranteed that all the positions are distinct.OutputPrint one integer — the minimum number of moves you have to make to place all the pieces in the cells of the same color.Examples6 1 2 6210 1 2 3 4 510NoteIn the first example the only possible strategy is to move the piece at the position 6 to the position 5 and move the piece at the position 2 to the position 3. Notice that if you decide to place the pieces in the white cells the minimum number of moves will be 3.In the second example the possible strategy is to move $5\rightarrow9$ in 4 moves, then $4\rightarrow7$ in 3 moves, $3 \rightarrow 5$ in 2 moves and $2 \rightarrow 3$ in 1 move.链接http://codeforces.com/contest/985/problem/A题意给定一个1*n的棋盘，n是偶数，棋盘的布局是“黑白黑白黑白…”，现有$\frac{n}{2}$个棋子摆放在不同的位置，问将这些棋子移到全黑或者全白的位置需要的最少移动次数。题解数据范围小，手动模拟一遍，得到将所有的棋子移动到全黑的位置次数sum1，移动到全白位置次数sum2，答案为两者最小值。代码Accepted31 ms0 KB#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include…

Gym 100803C Shopping（贪心）
type: item
date: 2018-05-19T23:27:00+08:00
description: ShoppingYour friend will enjoy shopping. She will walk through a mall along a straight street, where N individual shops (numbered from 1 to N) are aligned at regular intervals. Each shop has one door and is located at the one side of the street. The distances between the doors of the adjacent shops are the same length, i.e. a unit length. Starting shopping at the entrance of the mall, she visits shops in order to purchase goods. She has to go to the exit of the mall after shopping. She requires some restrictions on visiting order of shops. Each of the restrictions indicates that she shall visit a shop before visiting another shop. For example, when she wants to buy a nice dress before choosing heels, she shall visit a boutique before visiting a shoe store. When the boutique is farther than the shoe store, she must pass the shoe store before visiting the boutique, and go back to the shoe store after visiting the boutique. If only the order of the visiting shops satisfies all the restrictions, she can visit other shops in any order she likes. Write a program to determine the minimum required walking length for her to move from the entrance to the exit. Assume that the position of the door of the shop numbered k is k units far from the entrance, where the position of the exit is N + 1 units far from the entrance.InputThe input file contains several test cases, each of them as described below. Each case input consists of a set of lines. N m c1 d1 .. . cm dm The first line contains two integers N and m, where N (1 ≤ N ≤ 1000) is the number of shops, and m (0 ≤ m ≤ 500) is the number of restrictions. Each of the next m lines contains two integers ci and di (1 ≤ ci < di ≤ N) indicating the i-th restriction on the visiting order, where she must visit the shop numbered ci after she visits the shop numbered di (i = 1, . . . , m). There are no pair of j and k that satisfy cj = ck and dj = dk.OutputFor each test case, output the minimum required walking length for her to move f…