A. CME
Description
Solution
B. Strings Equalization
Description
Solution
C. Save the Nature
Description
给出一个长为n序列A，A[i]=x表示第i次卖出的物品的价值为x，你可以任意交换其中的值。
给出$a,b,x,y$，表示第$a，2a,3a...$，$b,2b,3b,...$卖出的物品可以分别获得x%，y%的利润。
问如何安排顺序可以使最少的售卖物品而获得不低于k的利润。
Solution
真的，最近总是遇见这种题。
贪心+二分。
首先，序列可以任意交换，那么如果卖出x个物品能使利润大于等于k，那么x+1个物品一定能达到。
就是说答案具有单调性。
那么考虑二分答案。（而且题目明确最小值最大，二分答案关键字hhh
在一个给定的答案p的检测中，我们首先满足lcm(a,b)的最大。
然后，如果x>y先满足a，否则先满足b
最后判断当前利润是否大于等于k。
1 #include <algorithm>
2 #include <cctype>
3 #include <cmath>
4 #include <cstdio>
5 #include <cstdlib>
6 #include <cstring>
7 #include <iostream>
8 #include <map>
9 #include <numeric>
10 #include <queue>
11 #include <set>
12 #include <stack>
13 #if __cplusplus >= 201103L
14 #include <unordered_map>
15 #include <unordered_set>
16 #endif
17 #include <vector>
18 #define lson rt << 1, l, mid
19 #define rson rt << 1 | 1, mid + 1, r
20 #define LONG_LONG_MAX 9223372036854775807LL
21 #define pblank putchar(' ')
22 #define ll LL
23 #define fastIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
24 using namespace std;
25 typedef long long ll;
26 typedef long double ld;
27 typedef unsigned long long ull;
28 typedef pair<int, int> P;
29 int n, m;
30 ll k;
31 const int maxn = 2e5 + 10;
32 template <class T>
33 inline T read()
34 {
35 int f = 1;
36 T ret = 0;
37 char ch = getchar();
38 while (!isdigit(ch))
39 {
40 if (ch == '-')
41 f = -1;
42 ch = getchar();
43 }
44 while (isdigit(ch))
45 {
46 ret = (ret << 1) + (ret << 3) + ch - '0';
47 ch = getchar();
48 }
49 ret *= f;
50 return ret;
51 }
52 template <class T>
53 inline void write(T n)
54 {
55 if (n < 0)
56 {
57 putchar('-');
58 n = -n;
59 }
60 if (n >= 10)
61 {
62 write(n / 10);
63 }
64 putchar(n % 10 + '0');
65 }
66 template <class T>
67 inline void writeln(const T &n)
68 {
69 write(n);
70 puts("");
71 }
72 ll c[maxn];
73 int x, y, a, b;
74 inline int judge(int mid){
75 ll cur = 0;
76 int l = 1;
77 for (int i = 1; i <= mid;i++)
78 if (i%a==0&&i%b==0)
79 cur += c[l++] * (x + y)/100;
80 for (int i = 1; i <= mid;i++)
81 if (i%b==0&&i%a!=0)
82 cur += c[l++] * y / 100;
83 for (int i = 1; i <= mid;i++)
84 if (i%a==0&&i%b!=0)
85 cur += c[l++] * x / 100;
86 return cur >= k;
87 }
88 int main(int argc, char const *argv[])
89 {
90 #ifndef ONLINE_JUDGE
91 freopen("in.txt", "r", stdin);
92 // freopen("out.txt", "w", stdout);
93 #endif
94 int t = read<int>();
95 while (t--)
96 {
97 n = read<int>();
98 for (int i = 1; i <= n; i++)
99 c[i] = read<ll>();
100 x = read<int>(), a = read<int>();
101 y = read<int>(), b = read<int>();
102 k = read<ll>();
103 sort(c + 1, c + 1 + n);
104 reverse(c + 1, c + 1 + n);
105 if (x>y)
106 swap(a, b), swap(x, y);
107 int l = 1, r = n, res = -1;
108 while (l<=r)
109 {
110 int mid = l + r >> 1;
111 if (judge(mid)){
112 res = mid;
113 r = mid - 1;
114 }
115 else
116 l = mid + 1;
117 }
118 writeln(res);
119 }
120 return 0;
121 }
View Code
D. Sequence Sorting
Description
给出一个长为n的序列，序列内的值x都满足$1 \leq x \leq n$。
我们可以执行操作，每次可以将序列内的等于k的数全部移到最前面或者最后面。
问最少执行多少次操作可以满足序列升序。
Solution
我怎么想不到，哭了。
对于一个序列内的每一个值，我们记录一个最早出现和最晚出现的索引$l[x],r[x]$
然后对序列进行排序去重。对去重后的序列进行查询。
如果$r[a[i-1]] \gt l[a[i]]$代表a[i-1]和a[i]需要交换位置，那么我们可以记录一个最长的连续不需要交换的序列，去重后的序列长度减去当前最长连续不需要交换就是需要被操作的次数
注意一点是不能直接通过$r[a[i-1]] \gt l[a[i]]$来记录需要操作的次数
考虑一个例子
1 3 2 4
如果通过第二种方式直接计算需要操作的次数，那么我们会得到答案1,(判断3和2得到的答案贡献1)
而真实答案应该2
1 #include <algorithm>
2 #include <cctype>
3 #include <cmath>
4 #include <cstdio>
5 #include <cstdlib>
6 #include <cstring>
7 #include <iostream>
8 #include <map>
9 #include <numeric>
10 #include <queue>
11 #include <set>
12 #include <stack>
13 #if __cplusplus >= 201103L
14 #include <unordered_map>
15 #include <unordered_set>
16 #endif
17 #include <vector>
18 #define lson rt << 1, l, mid
19 #define rson rt << 1 | 1, mid + 1, r
20 #define LONG_LONG_MAX 9223372036854775807LL
21 #define pblank putchar(' ')
22 #define ll LL
23 #define fastIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
24 using namespace std;
25 typedef long long ll;
26 typedef long double ld;
27 typedef unsigned long long ull;
28 typedef pair<int, int> P;
29 int n, m, k;
30 const int maxn = 3e5 + 10;
31 template <class T>
32 inline T read()
33 {
34 int f = 1;
35 T ret = 0;
36 char ch = getchar();
37 while (!isdigit(ch))
38 {
39 if (ch == '-')
40 f = -1;
41 ch = getchar();
42 }
43 while (isdigit(ch))
44 {
45 ret = (ret << 1) + (ret << 3) + ch - '0';
46 ch = getchar();
47 }
48 ret *= f;
49 return ret;
50 }
51 template <class T>
52 inline void write(T n)
53 {
54 if (n < 0)
55 {
56 putchar('-');
57 n = -n;
58 }
59 if (n >= 10)
60 {
61 write(n / 10);
62 }
63 putchar(n % 10 + '0');
64 }
65 template <class T>
66 inline void writeln(const T &n)
67 {
68 write(n);
69 puts("");
70 }
71 vector<int> a;
72 int l[maxn], r[maxn];
73 int main(int argc, char const *argv[])
74 {
75 #ifndef ONLINE_JUDGE
76 freopen("in.txt", "r", stdin);
77 // freopen("out.txt","w", stdout);
78 #endif
79 int t = read<int>();
80 while (t--)
81 {
82 n = read<int>();
83 a.clear();
84 for (int i = 1; i <= n; i++)
85 l[i] = 1e9, r[i] = 0;
86 for (int i = 1; i <= n; i++)
87 {
88 int x = read<int>();
89 a.emplace_back(x);
90 if (l[x] == 1e9)
91 l[x] = i;
92 r[x] = i;
93 }
94 sort(a.begin(), a.end());
95 a.erase(unique(a.begin(), a.end()), a.end());
96 int sz = a.size();
97 int res = 1;
98 int cur = 1;
99 for (int i = 1; i < sz; i++){
100 if (l[a[i]] > r[a[i-1]])
101 ++cur;
102 else
103 cur = 1;
104 res = max(res, cur);
105 }
106 writeln(sz-res);
107 }
108 return 0;
109 }
View Code