10pts求助,看不懂题解,感觉贪心的思路没问题@
查看原帖
10pts求助,看不懂题解,感觉贪心的思路没问题@
815075
hzy99999楼主2023/8/4 11:47
//1.若第一位不为1,无解
//2.升序排序
//3.计算下一数值-1至少要多少个硬币
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n;
LL a[N], m;
LL cnt;
int main()
{
	scanf("%d%lld", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	sort(a, a + n);
	if (a[0] != 1) {
		puts("No answer!!!");
		return 0;
	}
	for (int i = 1; i < n; i++)
	{
		if (m <= a[i] - 1)//m在a[i-1]与a[i]之间 
		{
			cnt += (m - (a[i - 1] - 1)) / a[i - 1];
			break;
		}
		else cnt += (a[i] - a[i - 1]) / a[i - 1];
	}
	if (m > a[n - 1] - 1)cnt += (m - (a[n - 1] - 1)) / a[n - 1];//m在a[n-1]-1之后
	printf("%lld\n", cnt);
	return 0;
}
2023/8/4 11:47
加载中...