CCF-CSP 29次第二题【202303-2 垦田计划】-Toy模板网

这篇具有很好参考价值的文章主要介绍了CCF-CSP 29次第二题【202303-2 垦田计划】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

法一：
70分：优先队列
对基础耗时大的优先进行处理

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m, k;
priority_queue<PII, vector<PII>, less<PII>> q;

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	
	int t_min = 1e8;
	for (int i = 0; i < n; i ++ )
	{
		int t, c;
		scanf("%d%d", &t, &c);
		q.push({t, c});
		t_min = min(t_min, t);
	}
	
	int sum = 0;
	while (q.size())
	{
		auto a = q.top();
		q.pop();
		
		int t = a.first, c = a.second;
		
		if (t >= k && (sum + c) <= m)
		{
			sum += c;
			t -- ;	
			q.push({t, c});
		}
		else 
		{
			q.push({t, c});
			break;
		}
		
	}

	cout << q.top().first << endl;

	return 0;
}

/*
4 9 2
6 1
5 1
6 2
7 1
*/

法二：
100分：二分答案

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m, k;
int t[N], c[N];

bool check(int mid)
{
	int sum = 0;
	for (int i = 0; i < n; i ++ )
		if (t[i] > mid)
			sum += (t[i] - mid) * c[i];
	if (sum <= m) return true;
	else return false; 
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	
	int maxt = 0;
	for (int i = 0; i < n; i ++ ) 
	{
		cin >> t[i] >> c[i]; 
		maxt = max(maxt, t[i]);
	}
	
	int l = k, r = maxt;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	
	cout << l << endl; 
	return 0;
}

/*
4 9 2
6 1
5 1
6 2
7 1
*/

法三：对法一的改进文章来源地址https://www.toymoban.com/news/detail-732733.html

100分：对相同耗时的区域合并处理
同样从耗时最多的区域开始

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m, k;
int t[N], c[N];
int cnt[N]; // 统计 不同耗时减少一天需要的资源总和 

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	
	int maxt = 0;
	for (int i = 0; i < n; i ++ ) 
	{
		cin >> t[i] >> c[i]; 
		maxt = max(maxt, t[i]);
		cnt[t[i]] += c[i];
	}
	
	int i = 0;
	for (i = maxt; i >= k; i -- )
	{
		if (cnt[i] > m) break;
		m -= cnt[i];
		cnt[i - 1] += cnt[i];
	}
	
	cout << i << endl;
	
	return 0;
}

/*
4 9 2
6 1
5 1
6 2
7 1
*/

到了这里，关于CCF-CSP 29次第二题【202303-2 垦田计划】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！