LeetCode435. Non-overlapping Intervals（贪心 / 动态规划）
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 Intervals.bool cmp(const Interval & a, const Interval & b) { if (a.start != b.start) return a.start < b.start; return a.end < b.end; } class Solution { public: int eraseOverlapIntervals(vector<Interval>& intervals) { int n = intervals.size(); if (n == 0) return 0; sort(intervals.begin(), intervals.end(), cmp); vector <int> dp(n + 1, 1); for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (intervals[i].start >= intervals[j].end) dp[i] = max(dp[i], dp[j] + 1); } } int ans = 0; for (int i = 0; i < n; ++i) ans = max(ans, dp[i]); return n - ans; } };The end.2019年4月11日 星期四
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; } };Runtime: 876 ms, faster than 5.04% of C++ online submissions for Assign Cookies.Memory Usage: 10.1 MB, less than 100.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(); vector<bool>vis(m + 1, false); sort(g.begin(), g.end()); sort(s.begin(), s.end()); int ans = 0; for (int i = n - 1; i >= 0; --i) { for (int j = m - 1; j >= 0; --j) { if (!vis[j] && s[j] >= g[i]) { ++ans; vis[j] = true; break; } } } return ans; } };The end.2019年4月11日 星期四
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[maxn]; int main() { int T, n; scanf("%d", &T); while (T--) { scanf("%d", &n); ll ans = 0, cnt = 0; bool flag = false; for (int i = 0; i < n; ++i) scanf("%lld", &a[i]); for (int i = 0; i < n - 1; ++i) { if (a[i + 1] > a[i]) // 低买高卖 { ans += a[i + 1] - a[i]; if (!flag) // 连续上升区间数量 cnt++; flag = true; } else if (a[i + 1] < a[i]) flag = false; } printf("%lld %lld\n", ans, cnt * 2); } return 0; }The end.2018-08-27 星期一
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记录可购买的升值股数 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; int main() { int n; scanf("%d", &n); ll money = 100, curprice = 100, number = 0, x = 0; for (int i = 0; i < n; ++i) { scanf("%lld", &x); if (x <= curprice) // 低价 { number = money / x; // 可购买数量 curprice = x; // 当前价格 } if (number > 100000) // 数量超出限制 number = 100000; if (x > curprice) // 高价 { money += number * (x - curprice); // 利润 curprice = x; } } printf("%lld\n", money); return 0; }The end.2018-08-27 星期一
HDU6438 Buy and Resell（贪心+优先队列/multiset）
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 = 0Source2018中国大学生程序设计竞赛 - 网络选拔赛题意给你接下来n天的交易价格，每天可以买进一个或者卖出一个或者什么都不做，问n天之后能获得的最大利润，并要求交易次数最少，假设一开始什么都没有，但是钱足够多。题解和CF866D Buy Low Sell High基本上一样，加了一个最少交易次数的限制，貌似之前湖南多校和牛客多校都出过类似的题。思考一个问题，怎么才能获得收益？当然是低价买入高价卖出，但是问题是如果现在就卖出了后面可能会有更高的价格可以卖出。怎么解决这个问题呢？我们可以用一个优先队列（从小到大排序）代表当前所持有的所有股票，枚举每个时候的股票价格，如果队首元素值小于当前枚举值，那么就可以卖出股票赚取利润，队首元素出队，但是注意需要把当前枚举值再次加入队列，因为被弹出的队首元素可能会和后面价格更高股票交易获取更多的利润，可以用当前枚举值与后面价格更高的股票交易，相当于当前枚举的股票没有进行操作。A 买入 B 卖出，B 买入 C 卖出等价于 A 买入 C 卖出，相当于 B 没有操作。比如2 5 9，5-2=3+9-5=4= 9+5-(5-2)=7。那么怎么才能交易次数最少呢，当然是在后面获取更大的利润时才算交易，使用一个标记数组，对当前交易的价格进行记录，如果队首元素被标记过，那么在后面获取更大的利润时交易次数就减一，相当于之前的交易没有进行，具体参见代码。#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> #include <algorithm> #include typedef long long ll; using namespace std; int main() { int T, n; ll x, ans1, ans2; multiset <ll> S; map <int, int> mp; scanf("%d", &T); while (T--) { scanf("%d", &n); ans1 = ans2 = 0; S.clear(); mp.clear(); for (int i = 0; i < n; ++i) { scanf("%lld", &x); S.insert(x); if (*S.begin() < x) // 队首元素小于当前价格 { ans2++; if (mp[*S.begin()] > 0) // 如果之前交易过次数减1 { ans2--; mp[*S.begin()]--; } ans1 += (x - * S.begin()); // 利润 S.erase(S.begin()); // 卖出 S.insert(x); // 再次加入，后面可能还有更高的利润 mp[x]++; // 标记 } } printf("%lld %lld\n", ans1, 2 * ans2); } return 0; }好像还有更神仙的写法。#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> #include <algorithm> typedef long long ll; using namespace std; int main() { int T, n; ll x, ans1, ans2; multiset <pair<ll, int> > S; scanf("%d", &T); while (T--) { scanf("%d", &n); ans1 = ans2 = 0; S.clear(); for (int i = 0; i < n; ++i) { scanf("%lld", &x); S.insert(make_pair(x, 0)); // 买入状态 S.insert(make_pair(x, 1)); // 卖出状态 ans1 += (x - S.begin()->first); if (S.begin()->second == 1) // 卖出时操作*2 ans2 += 2; S.erase(S.begin()); } printf("%lld %lld\n", ans1, ans2); } return 0; }当然本题也可以使用优先队列完成，可以重载或者存入相反数，就相当于从小到大排序。The end.2018-08-27 星期一
Codeforces Round #437 (Div. 1)D Buy Low Sell High（贪心+优先队列/multiset）
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) { ans += x - Q.top(); Q.pop(); Q.push(x); } } // printf("%lld\n", ans); cout << ans << endl; return 0; }写法二Accepted 234 ms 9600 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; multiset <ll> S; cin >> n; for (int i = 0; i < n; ++i) { scanf("%lld", &x); S.insert(x); if (*S.begin() < x) { ans += x - *S.begin(); S.erase(S.begin()); S.insert(x); } } cout << ans << endl; return 0; }看上去multiset比优先队列更费内存和时间。The end.2018-08-27 星期一
Educational Codeforces Round 44 (Div. 2)（模拟+贪心）
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 <algorithm> using namespace std; const int maxn = 110; int a[maxn]; int main() { int n, b = 1, w = 2; int sum1 = 0, sum2 = 0; scanf("%d", &n); for (int i = 1; i <= n / 2; ++i) scanf("%d", &a[i]); sort(a + 1, a + 1 + n / 2); for (int i = 1; i <= n / 2; ++i) { sum1 += abs(b - a[i]); // 全黑 sum2 += abs(w - a[i]); // 全白 b += 2, w += 2; } printf("%d\n", min(sum1, sum2)); return 0; }B. Switches and Lamps（模拟）time limit per test：3 secondsmemory limit per test：256 megabytesYou are given n switches and m lamps. The i-th switch turns on some subset of the lamps. This information is given as the matrix a consisting of n rows and m columns where $a_{i, j} = 1$ if the i-th switch turns on the j-th lamp and $a_{i, j} = 0$ if the i-th switch is not connected to the j-th lamp.Initially all m lamps are turned off.Switches change state only from "off" to "on". It means that if you press two or more switches connected to the same lamp then the lamp will be turned on after any of this switches is pressed and will remain its state even if any switch connected to this lamp is pressed afterwards.It is guaranteed that if you push all n switches then all m lamps will be turned on.Your think that you have too many switches and you would like to ignore one of them.Your task is to say if there exists such a switch that if you will ignore (not use) it but press all the other n - 1 switches then all the m lamps will be turned on.InputThe first line of the input contains two integers n and m (1 ≤ n, m ≤ 2000) — the number of the switches and the number of the lamps.The following n lines contain m characters each. The character $a_{i, j}$ is equal to '1' if the i-th switch turns on the j-th lamp and '0' otherwise.It is guaranteed that if you press all n switches all m lamps will be turned on.OutputPrint "YES" if there is a switch that if you will ignore it and press all the other n - 1 switches then all m lamps will be turned on. Print "NO" if there is no such switch.Examples4 5 10101 01000 00111 10000YES4 5 10100 01000 00110 00101NO链接http://codeforces.com/contest/985/problem/B题意有n个开关和m个灯泡，一个开关能控制多个灯泡，保证使用n个开关可以控制所有的灯泡。现在问能否使用n-1开关控制所有的灯泡。题解从每行开始遍历，如果去掉某行后，剩余开关能控制所有的灯泡则直接结束循环输出YES，遍历完后还是不能则输出NO，具体参见代码。代码Accepted46 ms19800 KB#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 2010; char s[maxn][maxn]; int a[maxn][maxn]; int sum[maxn]; int main() { int n, m; scanf("%d%d", &n, &m); memset(sum, 0, sizeof(sum)); for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { a[i][j] = ((s[i][j] == '1') ? 1 : 0); sum[j] += a[i][j]; // 统计每个灯泡可以被多少个开关控制 } bool flag = false; for (int i = 1; i <= n; ++i) { int j; for (j = 1; j <= m; ++j) { if (sum[j] - a[i][j] == 0) // 去除该开关后，没有别的开关可以控制该灯泡 break; } if (j > m) // 去除该开关后没有问题 { flag = true; break; } } if (flag) printf("YES\n"); else printf("NO\n"); return 0; }C. Liebig's Barrels（贪心）time limit per test：2 secondsmemory limit per test：256 megabytesYou have m = n·k wooden staves. The i-th stave has length $a_i$. You have to assemble n barrels consisting of k staves each, you can use any k staves to construct a barrel. Each stave must belong to exactly one barrel.Let volume $v_j$ of barrel j be equal to the length of the minimal stave in it.You want to assemble exactly n barrels with the maximal total sum of volumes. But you have to make them equal enough, so a difference between volumes of any pair of the resulting barrels must not exceed l, i.e. $|v_x - v_y| ≤ l$ for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.Print maximal total sum of volumes of equal enough barrels or 0 if it's impossible to satisfy the condition above.InputThe first line contains three space-separated integers n, k and l ($1 ≤ n, k ≤ 10^5, 1 ≤ n·k ≤ 10^5, 0 ≤ l ≤ 10^9$).The second line contains m = n·k space-separated integers $a_1, a_2, ..., a_m (1 ≤ a_i ≤ 10^9)$ — lengths of staves.OutputPrint single integer — maximal total sum of the volumes of barrels or 0 if it's impossible to construct exactly n barrels satisfying the condition $|v_x - v_y| ≤ l$ for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.Examples4 2 1 2 2 1 2 3 2 2 372 1 0 10 10201 2 1 5 223 2 1 1 2 3 4 5 60NoteIn the first example you can form the following barrels: [1, 2], [2, 2], [2, 3], [2, 3].In the second example you can form the following barrels: [10], [10].In the third example you can form the following barrels: [2, 5].In the fourth example difference between volumes of barrels in any partition is at least 2 so it is impossible to make barrels equal enough.链接http://codeforces.com/contest/985/problem/C题意有n*k块木板，让你用k块木板组成一个木桶，总共组成n个，每个桶的体积为最短木板的长度，现要求n个木桶中任意两个的体积之差不能超过l，求n个桶的最大体积。题解贪心思想，每个木桶的体积都由组成它的最短木板的长度决定，所以只需考虑每个木桶中的最短木板。首先对n*k块木板进行排序（数组下标从第一个开始），如果a[n]-a[1]大于l，那么输出0。然后找到排序后序列中最后一个小于等于a[1]+l的木板p的位置，木板p是在范围之内能取得的最大体积。最后把K块木板中的最短木板加起来，再从第p块木板往前找符合要求的加起来，得到答案。本题参考了断腿三郎的题解。代码Accepted280 ms1800 KB#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 200010; bool vis[maxn]; ll a[maxn]; int main() { ll n, k, l, sum = 0, cnt = 0; cin >> n >> k >> l; for (int i = 1; i <= k * n; ++i) cin >> a[i]; sort(a + 1, a + 1 + k * n); if (a[n] - a[1] > l) { cout << "0\n"; return 0; } int p = k * n; // 注意p初始化的值 for (int i = n + 1; i <= n * k; ++i) // 找到最后一个小于等于a[1] + k的 if (a[i] - a[1] > l) { p = i - 1; break; } bool flag = false; for (int i = 1; i <= p; i += k) // 范围之内，每k个取一个最小的 { sum += a[i]; vis[i] = true; cnt++; if (cnt == n) { flag = true; break; } } if (flag) cout << sum << "\n"; else { for (int i = p; i >= 1; --i) // 从最后一个开始选择剩余符合要求的 { if (!vis[i]) { sum += a[i]; cnt++; if (cnt == n) { cout << sum << "\n"; break; } } } } return 0; }话说Clion的scanf和printf输入输出64位只能用%lld么，用%I64d的时候莫名出bug。The end.2018-05-25 星期五
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 from the entrance to the exit. You should omit the length of her walk in the insides of shops.Sample Input10 3 3 7 8 9 2 5 10 3 8 9 6 7 2 4 10 0Sample Output23 19 11链接https://vjudge.net/problem/Gym-100803C题意一条直线上有n个点，标号从1到n，起点为0，终点为N+1，给定m个限制关系（ci，di），访问ci点前必须先访问di点，每两个点之间是单位距离，求在限制条件下，从起点到终点访问完所有的点的最短距离。题解画图模拟一下可知，从起点0到终点的N+1这段距离是必须的，若想距离最短，必须去重。比如以下样例：10 33 78 92 5试模拟一下按部就班的访问，从0开始，先访问5，再访问2，->7->3->9->8->11,最后结束，因为要满足限制条件，会重走一些路，有些重走是不可避免的，比如限制条件8 9,为了先访问9再访问8，必须将8~9这一段走2遍，但是限制条件2 5和3 7则不然，不必要将2~5和3~7都重走2遍，画图显然可知，只需将2~7重走2遍就可同时满足这两个限制条件，也就是说，如果两个限制条件走过的路有交叉（可能是包含）的话，那么取并集即可。参考自UVaLive6834 Shopping。代码Accepted31 ms0 KB#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 510; struct node { int l, r; }a[maxn]; bool cmp(node x, node y) { if (x.r == y.r) return x.l > y.l; return x.r > y.r; } int main() { int n, m, ans, L, R; while (scanf("%d%d", &n, &m) != EOF) { ans = n + 1; for (int i = 0; i < m; ++i) scanf("%d%d", &a[i].l, &a[i].r); sort(a, a + m, cmp); // 排序 L = a[0].l, R = a[0].r; for (int i = 1; i < m; ++i) { if (a[i].r >= L) // 合并区间 L = min(a[i].l, L); else // 无重合则处理后更新 { ans += (R - L) * 2; L = a[i].l, R = a[i].r; } } ans += (R - L) * 2; printf("%d\n", ans); } return 0; }The end.2018-05-19 星期六