A. Upload More RAM
思路:
题目要我们上传nGB的内容，但是每k秒我们最多上传1GB，所以只要求出前（n-1）GB上传的时间，然后在加上上传最后1GB所用的1秒。
代码:
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define mod 1000000007
#define inf 1e9+7
typedef long long ll;
ll n, m, t, k, cnt = 1, ans, sum, minn = inf, maxx = 0;
ll x, y, z;
ll s1, s2;
ll a[N], b[N], c[N], dp[N],f[110][3005];
bool vis[N], flag;
typedef pair<int, int>pii;
string s;
void solve()
{cin >> n >> m;cout << n * m - (m - 1) << endl;
}
int main()
{cin >> t;while (t--) {solve();}return 0;
}B.K-Sort
思路:
每次可以给k个硬币添加1个硬币，但是代价是k+1的，要求最后需要最小多少的代价可以将其变成一个非减数列。所以，我们需要求出每个递减的序列中与最大值的差值，然后排序，从小到大，对第i个差值，代价是k-i+1。
代码:
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define mod 1000000007
#define inf 1e9+7
typedef long long ll;
ll n, m, t, k, cnt=0, ans, sum, minn = inf, maxx = 0;
ll x, y, z;
ll s1, s2;
ll a[N], b[N], c[N], dp[N],f[110][3005];
bool vis[N], flag;
typedef pair<int, int>pii;
string s;
void solve()
{cin >> n;cnt = 0, ans = 0, maxx = 0;for (int i = 1; i <= n; i++) {cin >> dp[i];}for (int i = 1; i <= n; i++) {cnt = max(dp[i], cnt);if (i >= 2&&dp[i]<cnt) {ans += cnt-dp[i];maxx = max(cnt - dp[i], maxx);}}cout << ans + maxx << endl;
}
int main()
{cin >> t;while (t--) {solve();}return 0;
}C. Basil's Garden
思路:
给定n朵花，每秒有风吹过来使得hi > hi+1 的花高度减一，问经过多长时间所有花的高度降低为0。那么对于第i朵花，如果其高度hi<=hi+1则其高度降低为零用时为hi+1+1；如果其高度hi>hi+1，那么第i朵花高度降低为零的时间为max(hi+1+1,hi)。
代码:
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define mod 1000000007
#define inf 1e9+7
typedef long long ll;
ll n, m, t, k, cnt=0, ans, sum, minn = inf, maxx = 0;
ll x, y, z;
ll s1, s2;
ll a[N], b[N], c[N], dp[N],f[110][3005];
bool vis[N], flag;
typedef pair<int, int>pii;
string s;
void solve()
{cin >> n;for (int i = 1; i <= n; i++)cin >> dp[i];for (int i = n - 1; i >= 1; i--) {if (dp[i] <= dp[i + 1])dp[i] = dp[i + 1] + 1;}cout << dp[1] << endl;
}
int main()
{cin >> t;while (t--) {solve();}return 0;
}
