Codeforce 980 Div2 A-D 题解

A. Profitable Interest Rate

原题

A. Profitable Interest Rate

思路

易推出公式 2 * a - b

代码

#include <bits/stdc++.h>
//#define int long long#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;int n, m, k, x, y, z, ans, t;
int w[N], f[N];void solve()
{int a, b;cin >> a >> b;if (a >= b)cout << a << endl;else{cout << max(0, (2 * a - b)) << endl;}
}signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T -- ){solve();}
}

B. Buying Lemonade

原题

B. Buying Lemonade

思路

这道题的思维多一点, 我们去求所有饮料机里剩余饮料最少的饮料机还剩多少罐饮料, 设此为 x, 然后所有饮料机都拿 x 罐

每次拿完 x 罐后, 下一次拿就可能会拿到那个空的饮料机, 这里加1

答案是需要的 k 罐饮料加上按倒空饮料机多按的次数

x 可以用差分得到

代码

#include <bits/stdc++.h>
#define int long long#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;int n, m, k, x, y, z, ans, t;
int w[N], f[N];void solve()
{cin >> n >> k;for (int i = 1; i <= n; i ++ ){cin >> w[i];}sort(w + 1, w + n + 1);for (int i = 1; i <= n; i ++ ){f[i] = w[i] - w[i - 1];}ans = 0;x = 0;for (int i = 1; i <= n; i ++ ){if (i != 1) ans ++;x += f[i] * (n - i + 1);if (x >= k) break;}cout << ans + k << endl;
}signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T -- ){solve();}
}

C. Concatenation of Arrays

原题

C. Concatenation of Arrays

 

思路

贪心的排序

按i + j 来排序即可

代码

#include <bits/stdc++.h>
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 200005, M = (N << 1), mod = 1e9 + 7;int n, m, k, x, y, z, ans, t;
int w[N], f[N];pii a[N];bool cmp(pii a, pii b)
{int res1 = 0, res2 = 0;res1 = a.first + a.second;res2 = b.first + b.second;return res1 < res2;
}void solve()
{cin >> n;//	map<pii, int> mm;for (int i = 1; i <= n; i ++ ){cin >> a[i].first >> a[i].second;
//		mm[a[i]] = i;}sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; i ++ ){cout << a[i].first << " " << a[i].second << " ";}cout << "\n";
}signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T -- ){solve();}
}

D. Skipping

原题

D. Skipping

思路

这道题想着贪心去做, 浪费了大量时间, 就应该搜索去做

广度优先搜索, dp, 堆优化, 可以解决此题

代码

#include <bits/stdc++.h>
#define int long long#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;int n, m, k, x, y, z, ans, t;
int w[N], f[N];void solve()
{cin >> n;vector<int> a(n);for (int i = 0; i < n; i ++ ) cin >> a[i];vector<int> b(n);for (int i = 0; i < n; i ++ ){cin >> b[i];b[i] --;}vector<int> dp(n, inf);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;q.emplace(0, 0);while (!q.empty()){auto [d, i] = q.top();q.pop();if (dp[i] != inf){continue;}dp[i] = d;q.emplace(d + a[i], b[i]);if (i > 0){q.emplace(d, i - 1);}}int ans = 0, sum = 0;for (int i = 0; i < n; i ++ ){sum += a[i];ans = max(ans, sum - dp[i]);}cout << ans << endl;
}signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T -- ){solve();}
}