Codeforce 980 Div2 A-D 题解

A. Profitable Interest Rate

原题

A. Profitable Interest Rate

思路

易推出公式 2 * a - b

代码

#include 
//#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 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 
#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 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 
#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 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 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 
#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 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 a(n);
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	
	vector b(n);
	for (int i = 0; i < n; i ++ )
	{
		cin >> b[i];
		b[i] --;
	}
	
	vector dp(n, inf);
	
	priority_queue, vector>, 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();
	}
}