社区讨论

NOIPT1调不出来

学术版参与者 8已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@mj59y061
此快照首次捕获于
2025/12/14 13:18
2 个月前
此快照最后确认于
2025/12/14 14:18
2 个月前
查看原帖
rt,T1死活调不出来
贪心思路是先尽可能多买平均价格最低的糖果(按对计算),然后用剩余钱按从小到大的顺序购买每种糖果中最便宜的的第一颗糖果
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;

struct node{
	int x;
	int y;
	int sum;
}a[N];


bool cmp(node a,node b){
	if(a.sum != b.sum) return a.sum < b.sum;
	return a.x < b.x;
}

bool cmp2(node a,node b){
	return a.x < b.x;
}


signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		cin >> a[i].x >> a[i].y;
		a[i].sum = (a[i].x + a[i].y);
	}
	
	sort(a + 1,a + n + 1,cmp);
	
	int t = m,cnt = 0;
	
	cnt += 2 * (t / a[1].sum);
	t %= a[1].sum;
	
	sort(a + 1,a + n + 1,cmp2);
	
//	for(int i = 1;i <= n;i ++)
//		cout << a[i].x << " " << a[i].y << "\n";
	
	
	for(int i = 1;i <= n;i ++){
		if(t >= a[i].x){
			t -= a[i].x;
			cnt ++;
		} 
		else break;
	}
	
	cout << cnt;
	
	return 0;
}

排序那里比的是a[i].x+a[i].ya[i].x+a[i].y是因为比两个数的a[i].x+a[i].y/2a[i].x+a[i].y/2(平均价格)等于比a[i].x+a[i].ya[i].x+a[i].y
计算能买多少对平均价格最低的糖果也优化过了,O(1)O(1),不可能TLE
但现在只得了70分,WA掉了。我寻思我的思路也应该没错啊,求救qwq
另:我只是个五年级蒟蒻qwq,太菜了请轻喷蟹蟹

回复

12 条回复,欢迎继续交流。

正在加载回复...