1 条题解

  • 0
    @ 2026-1-16 21:54:21

    #include <bits/stdc++.h>
    #define EB emplace_back
    
    typedef long long ll;
    typedef std::pair <int, int> pr;
    typedef std::vector <pr> vector;
    const int N = 5054, L = 2000054;
    
    struct monster {
    	int h, a, d;
    	monster * read() {return scanf("%d%d%d", &h, &a, &d), this;}
    	inline int kill(int attack) {return (h - 1) / (attack - d) + 1;}
    } a[N], b[N];
    
    int n, CA, CD;
    ll fy[L];
    vector adjs[L];
    
    inline void up(int &x, const int y) {x < y ? x = y : 0;}
    
    int main() {
    	int i, j, k, l, m, attack, defense = 0, inf = 0, sup = 0, best_attack = 0, best_defense = 0;
    	ll ans = LLONG_MAX, delta = 0, health = 0, current, best_health = 0;
    	scanf("%d%d%d", &n, &CA, &CD);
    	for (i = 0; i < n; ++i) up(inf, a[i].read()->d), up(sup, a[i].h + a[i].d), up(defense, a[i].a);
    	for (++inf, i = 0; i < n; ++i) {
    		fy[a[i].a] += a[i].kill(inf), m = a[i].h - 1;
    		for (j = inf, l = -1; ; l = k, j = m / k + a[i].d + 1) {
    			k = m / (j - a[i].d);
    			if (~l) adjs[j].EB(a[i].a, k - l);
    			if (!k) break;
    		}
    	}
    	for (attack = inf; attack <= sup; ++attack) {
    		for (const pr &adj : adjs[attack])
    			if (fy[adj.first] += adj.second, defense < adj.first)
    				delta += adj.second, health += (adj.first - defense) * adj.second;
    		for (; defense > 1; health += delta += fy[defense--])
    			if (delta + fy[defense] >= CD) break;
    		current = health + (ll)CA * attack + (ll)CD * defense;
    		if (current <= ans)
    			ans = current, best_attack = attack, best_defense = defense, best_health = health;
    	}
    	printf("%lld %d %d\n", ++best_health, best_attack, best_defense);
    	return 0;
    }
    
    
    • 1

    信息

    ID
    5806
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者