【无标题】

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;
}