网站 建设平台分析网站建设与网页设计视频

网站 建设平台分析,网站建设与网页设计视频,新媒体 网站建设 影视,seo整站优化多少钱题目链接 题目大意 给定三个正整数 n,a,kn, a, kn,a,k#xff0c;其中#xff1a; nnn 为怪物的数量#xff0c;nnn 个怪物站成一排#xff0c;从左到右编号 111 到 nnn#xff1b;aaa 为 nnn 个怪物的血量和#xff0c;且每个怪物的血量都是正数#xff1b;kkk 为小苯…题目链接题目大意给定三个正整数n , a , k n, a, kn,a,k其中n nn为怪物的数量n nn个怪物站成一排从左到右编号1 11到n nna aa为n nn个怪物的血量和且每个怪物的血量都是正数k kk为小苯的操作次数。每次操作小红会选择一个或相邻两个怪物使得它们的血量各自− 1 -1−1。当怪物的血量≤ 0 \leq 0≤0时怪物被消灭相邻关系不会改变。小红一定会选择最优策略使用尽可能少的攻击次数消灭这些怪物。在这种情况下小苯希望小红能使用恰好k kk次攻击消灭所有的怪物。请你帮小苯找出一个可能的血量分配方案如果不行输出− 1 -1−1。数据范围1 ≤ n ≤ 2 ⋅ 1 0 5 , 1 \leq n \leq 2 \cdot 10^5,1≤n≤2⋅105,n ≤ a ≤ 1 0 9 , n \leq a \leq 10^9,n≤a≤109,1 ≤ k ≤ 1 0 9 . 1 \leq k \leq 10^9.1≤k≤109.Solution首先n 1 n 1n1时只能将a aa分配给一个怪物所以只要看是否有a k a kak。下面考虑n 1 n 1n1的情况。由于需要恰好k kk次操作所以我们需要找到操作次数的上下界。先找下界L LL。要想操作次数接近下界L LL就要尽可能让小红选择相邻两个怪物一起扣血首先为每个怪物分配1 11生命值这样还剩下a − n a - na−n的血量和然后我们再分配⌊ a − n 2 ⌋ \left\lfloor \dfrac{a - n}{2} \right\rfloor⌊2a−n​⌋给怪物1 11分配⌈ a − n 2 ⌉ \left\lceil \dfrac{a - n}{2} \right\rceil⌈2a−n​⌉给怪物2 22。当n nn是偶数小红先通过n 2 \dfrac{n}{2}2n​次操作消除下面分配的1 11生命值然后再通过⌈ a − n 2 ⌉ \left\lceil \dfrac{a - n}{2} \right\rceil⌈2a−n​⌉次操作消灭怪物1 11和2 22操作次数为n 2 ⌈ a − n 2 ⌉ ⌈ a 2 ⌉ \dfrac{n}{2} \left\lceil \dfrac{a - n}{2} \right\rceil \left\lceil \dfrac{a}{2} \right\rceil2n​⌈2a−n​⌉⌈2a​⌉当n nn是奇数小红先通过⌈ n 2 ⌉ \left\lceil \dfrac{n}{2} \right\rceil⌈2n​⌉次操作消除下面分配的1 11生命值这时会影响到怪物2 22的血量会提前− 1 -1−1变为⌈ a − n 2 ⌉ − 1 ≤ ⌊ a − n 2 ⌋ \left\lceil \dfrac{a - n}{2} \right\rceil - 1 \leq \left\lfloor \dfrac{a - n}{2} \right\rfloor⌈2a−n​⌉−1≤⌊2a−n​⌋所以再通过⌊ a − n 2 ⌋ \left\lfloor \dfrac{a - n}{2} \right\rfloor⌊2a−n​⌋次操作就能消灭怪物1 11和2 22操作次数为⌈ n 2 ⌉ ⌊ a − n 2 ⌋ ⌊ n 1 2 ⌋ ⌊ a − n 2 ⌋ ⌊ a 1 2 ⌋ ⌈ a 2 ⌉ \left\lceil \dfrac{n}{2} \right\rceil \left\lfloor \dfrac{a - n}{2} \right\rfloor \left\lfloor \dfrac{n 1}{2} \right\rfloor \left\lfloor \dfrac{a - n}{2} \right\rfloor \left\lfloor \dfrac{a 1}{2} \right\rfloor \left\lceil \dfrac{a}{2} \right\rceil⌈2n​⌉⌊2a−n​⌋⌊2n1​⌋⌊2a−n​⌋⌊2a1​⌋⌈2a​⌉这样就说明操作次数下界L ⌈ a 2 ⌉ L \left\lceil \dfrac{a}{2} \right\rceilL⌈2a​⌉。再找上界R RR。要想操作次数接近上界R RR就要尽可能让小红只选择一个怪物扣血首先为每个怪物分配1 11生命值这样还剩下a − n a - na−n的血量和然后我们直接给怪物1 11分配a − n a - na−n的血量。当n nn是偶数小红先通过n 2 \dfrac{n}{2}2n​次操作消除下面分配的1 11生命值然后再通过a − n a - na−n次操作消灭怪物1 11操作次数为n 2 ( a − n ) a − n 2 a − ⌊ n 2 ⌋ \dfrac{n}{2} (a - n) a - \dfrac{n}{2} a - \left\lfloor \dfrac{n}{2} \right\rfloor2n​(a−n)a−2n​a−⌊2n​⌋当n nn是奇数小红先通过⌈ n 2 ⌉ \left\lceil \dfrac{n}{2} \right\rceil⌈2n​⌉次操作消除下面分配的1 11生命值这时怪物1 11不受影响还剩a − n a - na−n的血量值我们再通过a − n a - na−n次操作消灭怪物1 11操作次数为⌈ n 2 ⌉ ( a − n ) a − ⌊ n 2 ⌋ \left\lceil \dfrac{n}{2} \right\rceil (a - n) a - \left\lfloor \dfrac{n}{2} \right\rfloor⌈2n​⌉(a−n)a−⌊2n​⌋这样就说明操作次数上界R a − ⌊ n 2 ⌋ R a - \left\lfloor \dfrac{n}{2} \right\rfloorRa−⌊2n​⌋。所以只有当⌈ a 2 ⌉ ≤ k ≤ a − ⌊ n 2 ⌋ \left\lceil \dfrac{a}{2} \right\rceil \leq k \leq a - \left\lfloor \dfrac{n}{2} \right\rfloor⌈2a​⌉≤k≤a−⌊2n​⌋时才有可能构造一个合法分配。考虑从上界R a − ⌊ n 2 ⌋ R a - \left\lfloor \dfrac{n}{2} \right\rfloorRa−⌊2n​⌋开始调整。此时怪物1 11除了底部的1 11血量值还有额外分配的a − n a - na−n血量值我们将其拿出s ss来分配给怪物2 22这样怪物1 11的额外血量为a − n − s a - n - sa−n−s怪物2 22的额外血量为s ss。接着考虑这种分配下的操作次数。当n nn是偶数需要满足a − n − s ≥ s a - n - s \geq sa−n−s≥s即s ≤ ⌊ a − n 2 ⌋ s \leq \left\lfloor \dfrac{a - n}{2} \right\rfloors≤⌊2a−n​⌋小红先通过n 2 \dfrac{n}{2}2n​次操作消除下面分配的1 11生命值然后再通过a − n − s a - n - sa−n−s次操作消灭怪物1 11和2 22操作次数为n 2 ( a − n − s ) a − n 2 − s a − ⌊ n 2 ⌋ − s \dfrac{n}{2} (a - n - s) a - \dfrac{n}{2} - s a - \left\lfloor \dfrac{n}{2} \right\rfloor- s2n​(a−n−s)a−2n​−sa−⌊2n​⌋−s当n nn是奇数需要满足a − n − s ≥ s − 1 a - n - s \geq s - 1a−n−s≥s−1即s ≤ ⌊ a − n 1 2 ⌋ ⌈ a − n 2 ⌉ s \leq \left\lfloor \dfrac{a - n 1}{2} \right\rfloor \left\lceil\dfrac{a - n}{2} \right\rceils≤⌊2a−n1​⌋⌈2a−n​⌉小红先通过⌈ n 2 ⌉ \left\lceil \dfrac{n}{2} \right\rceil⌈2n​⌉次操作消除下面分配的1 11生命值这时怪物2 22受到影响还剩s − 1 s - 1s−1的血量值我们再通过a − n − s a - n - sa−n−s次操作消灭怪物1 11和2 22操作次数为⌈ n 2 ⌉ ( a − n − s ) a − ⌊ n 2 ⌋ − s \left\lceil \dfrac{n}{2} \right\rceil (a - n - s) a - \left\lfloor \dfrac{n}{2} \right\rfloor - s⌈2n​⌉(a−n−s)a−⌊2n​⌋−s综上操作次数为a − ⌊ n 2 ⌋ − s a - \left\lfloor \dfrac{n}{2} \right\rfloor - sa−⌊2n​⌋−s。于是令k a − ⌊ n 2 ⌋ − s k a - \left\lfloor \dfrac{n}{2} \right\rfloor- ska−⌊2n​⌋−s得到s a − ⌊ n 2 ⌋ − k . s a - \left\lfloor \dfrac{n}{2} \right\rfloor - k.sa−⌊2n​⌋−k.接下来只要验证这个解是否满足条件。当n nn为偶数需要满足s ≤ ⌊ a − n 2 ⌋ s \leq \left\lfloor \dfrac{a - n}{2} \right\rfloors≤⌊2a−n​⌋当a aa为偶数左式s a − n 2 − k s a - \dfrac{n}{2} - ksa−2n​−k右式a − n 2 \dfrac{a - n}{2}2a−n​作差得到a 2 − k ⌈ a 2 ⌉ − k ≤ 0 \dfrac{a}{2} - k \left\lceil \dfrac{a}{2} \right\rceil - k \leq 02a​−k⌈2a​⌉−k≤0当a aa为奇数左式a − n 2 − k a - \dfrac{n}{2} - ka−2n​−k右式a − n − 1 2 \dfrac{a - n - 1}{2}2a−n−1​作差得到a 1 2 − k ⌈ a 2 ⌉ − k ≤ 0 \dfrac{a 1}{2} - k \left\lceil \dfrac{a}{2} \right\rceil - k \leq 02a1​−k⌈2a​⌉−k≤0当n nn为奇数需要满足s ≤ ⌈ a − n 2 ⌉ s \leq \left\lceil\dfrac{a - n}{2} \right\rceils≤⌈2a−n​⌉当a aa为奇数左式a − n − 1 2 − k a - \dfrac{n - 1}{2} - ka−2n−1​−k右式a − n 2 \dfrac{a - n}{2}2a−n​作差得到a 1 2 − k ⌈ a 2 ⌉ − k ≤ 0 \dfrac{a 1}{2} - k \left\lceil \dfrac{a}{2} \right\rceil - k \leq 02a1​−k⌈2a​⌉−k≤0当a aa为偶数左式a − n − 1 2 − k a - \dfrac{n - 1}{2} - ka−2n−1​−k右式a − n 1 2 \dfrac{a - n 1}{2}2a−n1​作差得到a 2 − k ⌈ a 2 ⌉ − k ≤ 0 \dfrac{a}{2} - k \left\lceil \dfrac{a}{2} \right\rceil - k \leq 02a​−k⌈2a​⌉−k≤0综上解s a − ⌊ n 2 ⌋ − k s a - \left\lfloor \dfrac{n}{2} \right\rfloor - ksa−⌊2n​⌋−k合法。那么额外分配给怪物1 11的为a − n − s k − ⌈ n 2 ⌉ a - n - s k - \left\lceil \dfrac{n}{2} \right\rceila−n−sk−⌈2n​⌉怪物2 22的为a − ⌊ n 2 ⌋ − k a - \left\lfloor \dfrac{n}{2} \right\rfloor - ka−⌊2n​⌋−k。C Code#includebits/stdc.hintmain(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);intn,a,k;std::cinnak;if(n1){std::cout(ak?a:-1)\n;return0;}if((a1)/2kora-n/2k){std::cout-1\n;return0;}std::vectorans(n,1);ans[0]k-(n1)/2;ans[1]a-k-n/2;for(inti0;in;i){std::coutans[i] \n[in-1];}return0;}