A. Arrays
You are given two arrays A and B consisting of integers, sorted in non-decreasing order. Check whether it is possible to choose k numbers in array A and choose m numbers in array B so that any number chosen in the first array is strictly less than any number chosen in the second array.
Input
The first line contains two integers nA, nB (1 ≤ nA, nB ≤ 105), separated by a space — the sizes of arrays A and B, correspondingly.
The second line contains two integers k and m (1 ≤ k ≤ nA, 1 ≤ m ≤ nB), separated by a space.
The third line contains nA numbers a1, a2, ... anA ( - 109 ≤ a1 ≤ a2 ≤ ... ≤ anA ≤ 109), separated by spaces — elements of array A.
The fourth line contains nB integers b1, b2, ... bnB ( - 109 ≤ b1 ≤ b2 ≤ ... ≤ bnB ≤ 109), separated by spaces — elements of array B.
Output
Print "YES" (without the quotes), if you can choose k numbers in array A and m numbers in array B so that any number chosen in array A was strictly less than any number chosen in array B. Otherwise, print "NO" (without the quotes).
Sample test(s)
input
3 3
2 1
1 2 3
3 4 5
output
YES
input
3 3
3 3
1 2 3
3 4 5
output
NO
input
5 2
3 1
1 1 1 1 1
2 2
output
YES
Note
In the first sample test you can, for example, choose numbers 1 and 2 from array A and number 3 from array B (1 < 3 and 2 < 3).
In the second sample test the only way to choose k elements in the first array and m elements in the second one is to choose all numbers in both arrays, but then not all the numbers chosen in A will be less than all the numbers chosen in B: .
题目类型：简单贪心
算法分析：此时只要找A数组中第k个元素是否严格小于B数组从后面数的第m个元素即可
|
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-6; const double PI = 2 * acos (0.0); const int maxn = 4e6 + 66; int main() { // CPPFF; int n, m; cin >> n >> m; int ka, kb; cin >> ka >> kb; int sa, sb; for (int i = 1; i <= n; i++) { int tt; cin>> tt; if (i == ka) sa = tt; } for(int i = 1; i <= m; i++) { int tt; cin >> tt; if (i == m - kb + 1) sb = tt; } if (sa < sb) cout << "YES" << endl; else cout << "NO" << endl; return 0; } |
B.Order Book
In this task you need to process a set of stock exchange orders and use them to create order book.
An order is an instruction of some participant to buy or sell stocks on stock exchange. The order number i has pricepi, direction di — buy or sell, and integer qi. This means that the participant is ready to buy or sell qi stocks at pricepi for one stock. A value qi is also known as a volume of an order.
All orders with the same price p and direction d are merged into one aggregated order with price p and direction d. The volume of such order is a sum of volumes of the initial orders.
An order book is a list of aggregated orders, the first part of which contains sell orders sorted by price in descending order, the second contains buy orders also sorted by price in descending order.
An order book of depth s contains s best aggregated orders for each direction. A buy order is better if it has higher price and a sell order is better if it has lower price. If there are less than s aggregated orders for some direction then all of them will be in the final order book.
You are given n stock exhange orders. Your task is to print order book of depth s for these orders.
Input
The input starts with two positive integers n and s (1 ≤ n ≤ 1000, 1 ≤ s ≤ 50), the number of orders and the book depth.
Next n lines contains a letter di (either 'B' or 'S'), an integer pi (0 ≤ pi ≤ 105) and an integer qi (1 ≤ qi ≤ 104) — direction, price and volume respectively. The letter 'B' means buy, 'S' means sell. The price of any sell order is higher than the price of any buy order.
Output
Print no more than 2s lines with aggregated orders from order book of depth s. The output format for orders should be the same as in input.
Sample test(s)
input
6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10
output
S 50 8
S 40 1
B 25 10
B 20 4
Note
Denote (x, y) an order with price x and volume y. There are 3 aggregated buy orders (10, 3), (20, 4), (25, 10) and two sell orders (50, 8), (40, 1) in the sample.
You need to print no more than two best orders for each direction, so you shouldn't print the order (10 3) having the worst price among buy orders.
题目类型：简单模拟
算法分析：直接将所有S和B的操作能合并的就合并在一起，然后一个从小到大输出满足条件的数，另一个从大到小输出满足条件的数
|
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-6; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 66; int aa[maxn], bb[maxn]; int vala[maxn], valb[maxn], len; int main() { // CPPFF; int n, s; cin >> n >> s; string ss; int a, b; memset (aa, 0, sizeof (aa)); memset (bb, 0, sizeof (bb)); for (int i =1; i <= n; i++) { cin >> ss >> a >> b; if (ss == "B") { bb[a] += b; } else { aa[a] += b; } } len = 0; for (int i = 1, cnt = 1; cnt <= s && i <= 100000; i++) { if (aa[i]) { cnt++; vala[len] = i; valb[len++] = aa[i]; } } for (int i = len - 1; i >= 0; i--) cout << "S " << vala[i] << " " << valb[i] << endl; for (int i = 100000, cnt = 1; cnt <= s && i >= 0; i--) { if (bb[i]) { cout << "B " << i << " " << bb[i] << endl; cnt++; } } return 0; } |
C.Lengthening Sticks
You are given three sticks with positive integer lengths of a, b, and c centimeters. You can increase length of some of them by some positive integer number of centimeters (different sticks can be increased by a different length), but in total by at most l centimeters. In particular, it is allowed not to increase the length of any stick.
Determine the number of ways to increase the lengths of some sticks so that you can form from them a non-degenerate (that is, having a positive area) triangle. Two ways are considered different, if the length of some stick is increased by different number of centimeters in them.
Input
The single line contains 4 integers a, b, c, l (1 ≤ a, b, c ≤ 3·105, 0 ≤ l ≤ 3·105).
Output
Print a single integer — the number of ways to increase the sizes of the sticks by the total of at most l centimeters, so that you can make a non-degenerate triangle from it.
Sample test(s)
input
1 1 1 2
output
4
input
1 2 3 1
output
2
input
10 2 1 7
output
0
Note
In the first sample test you can either not increase any stick or increase any two sticks by 1 centimeter.
In the second sample test you can increase either the first or the second stick by one centimeter. Note that the triangle made from the initial sticks is degenerate and thus, doesn't meet the conditions.
题目类型：组合数学+枚举
算法分析：首先将所有的方案数计算出来，其实就是C (L + 3, 3)。然后再计算出不满足条件的方案数，两者相减即可。不满足条件的方案数可以分别枚举三条边作为最长的边，然后设定这个最长的边要大于等于另外两个边的和，此时就会得到一个关于相对较小的两条边的增量的不等式，此时再次使用组合计算出方案数，也就是C (k + 2, 2)
|
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-6; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 66; LL TT (LL a, LL b, LL c, LL L) { LL res = 0; for (LL i = 0; i <= L; i++) { LL ta = a + i; ta = min (L - i, ta - b - c); if (ta < 0) continue; res += (ta + 1) * (ta + 2) / 2; } return res; } int main() { // CPPFF; LL a, b, c, L; cin >> a >> b >> c >> L; LL res = (L + 1) * (L + 2) * (L + 3) / 6; res -= TT (a, b, c, L); res -= TT (b, a, c, L); res -= TT (c, a, b, L); cout << res << endl; return 0; } |
- sgu102：下一篇 »