题目链接

这个题很妙啊！

思维 + dp + 二分

分析

参考题解：

首先我们得明白题目在讲啥…我看了半天…
假设我方的伤害和血量分别为(a,b)，敌方为(c,d)；
总结能赢的条件就是：b/c > d/(n*a)，转换一下就是nab > cd；

最朴素的思想，对于每个怪物我们都去二分一下最少硬币，每次O(n)check一下；
时间复杂度是O(q*log©*n)，显然不行。
考虑优化：关键就是这个check太耗时了，如果每次能O(1)check就好了；

考虑dp预处理：
用dp[i]表示用i的硬币最大能造成多少伤害，那么显然dp[]数组是单调递增的；
如果能处理出dp数组，每次在上面二分一下就行了；
由于每种能选多个，所以我们先初始化dp，然后再去枚举个数；

关键是预处理的时间复杂度分析：
由于总花费不能超过C，我们先枚举花费i，再枚举数量j，限制条件就是i*j<=C；
具体的讲：
i=1时，j最多枚举到C/1
i=2时，j最多枚举到C/2
i=3时，j最多枚举到C/3
i=4时，j最多枚举到C/4
…
这样外面一层是O(n)，里面一层是C/1 + C/2 + C/3 + C/4 + …，是一个调和级数，可以证明是O(logC)的

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 1e6 + 7;
const int N = 2e6 + 7;
const int M = 4e6 + 7;
const int mod = 3*5*7*11*13*17*19*23;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

ll a[maxn];
ll dp[maxn];	//dp[i]表示用i的硬币最大能造成多少伤害
ll n,m,C;

int main()
{
	scanf("%lld %lld",&n,&C);
	for(int i=1;i<=n;i++)
	{
		ll c,d,h;
		scanf("%lld %lld %lld",&c,&d,&h);
		a[c] = d*h;
	}
	
	//dp预处理
	for(int i=1;i<=C;i++)
		if(a[i])
		{
			for(int j=1;j*i<=C;j++)
				dp[i*j] = max(dp[i*j], a[i]*j);
		}
	
	for(int i=1;i<=C;i++) dp[i] = max(dp[i], dp[i-1]);
	
	int m;
	ire(m);
	while(m--)
	{
		ll x,y;
		scanf("%lld %lld",&x,&y);
		ll num = x * y;
		
		int l = 1, r = C + 1;
		while(l < r)
		{
			int mid = l + r >> 1;
			if(dp[mid] > num) r = mid;
			else l = mid + 1;
		}
		
		if(r > C) r = -1;
		
		cout<<r<<' ';
	}
	
	return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108