小苯的刷怪笼【牛客tracker 每日一题】

小苯的刷怪笼时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小苯为了阻止小红继续前进选择将n nn个怪物排成一排来阻挡他这些怪物的血量之和为a aa小苯可以随意分配他们的血量不能为0 00。小红的每次攻击可以使一个或相邻的两个怪物血量减1 11。当怪物的血量小于等于0 00时怪物被消灭怪物被消灭后依然存在相邻关系不会被改变。小红一定会选择最优策略使用尽可能少的攻击次数消灭这些怪物。在这种情况下小苯希望小红能使用恰好k kk次攻击消灭所有的怪物。请你帮小苯找出一个可能的血量分配方案。输入描述第一行输入三个整数n , a , k ( 1 ≦ n ≦ 2 × 10 5 , n ≦ a ≦ 10 9 , 1 ≦ k ≦ 10 9 ) n,a,k(1≦n≦2×10^5,n≦a≦10^9,1≦k≦10^9)n,a,k(1≦n≦2×105,n≦a≦109,1≦k≦109)。输出描述如果无解请输出− 1 −1−1。否则输出n nn个正整数按顺序代表怪物的血量。如果存在多个解决方案您可以输出任意一个系统会自动判定是否正确。注意自测功能可能因此返回答案错误结果请自行检查答案正确性。示例1输入3 8 5输出3 3 2示例2输入3 10 1输出-1解题思路本题先推导攻击次数的上下界再构造合法血量序列。已知总血量为a aa每次攻击最少削减1点血量故最少攻击次数下界为a aa最多攻击次数为2 a − n 2a-n2a−n由逐个单点攻击得到。仅当a ≤ k ≤ 2 a − n a\le k\le 2a-na≤k≤2a−n时有解否则直接输出-1。构造方案先给所有怪物初始血量1剩余血量s a − n sa-nsa−n进行分配想要凑出恰好k kk次攻击利用相邻攻击可合并减伤的性质调整数值使得最优攻击次数等于k kk优先给靠前怪物分配多余血量快速构造出满足条件的正整数血量序列。总结核心逻辑确定攻击次数合法区间区间内可构造方案区间外无解基于基础1血量分配剩余数值。关键操作判定k kk是否在合法范围、初始化全1序列、分配剩余血量凑出指定攻击次数。效率保障线性构造序列时间复杂度O ( n ) O(n)O(n)轻松适配2 × 10 5 2\times10^52×105的数据范围。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n,a,k;cinnak;if(n1){cout((ak)?a:-1)endl;return;}ll da-k;if(d*2a){cout-1endl;return;}elseif(dn/2){cout-1endl;return;}else{ll xd-(n-2)/2;ll ya-x-n2;coutmax(x,y) min(x,y) ;for(ll i0;in-2;i)cout1 ;coutendl;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}