F：侏儒游戲
時間限制：1秒 記憶體限制： 128 MB
譯文描述
敵人及其龐大的軍隊正在逼近您的堡壘，而您所要捍衛的只是一群守衛地精，贏得這場戰斗是沒有希望的，所以您的重點將放在對敵人造成盡可能多的傷害上，
您有n個侏儒可供使用，在戰斗之前，必須將它們最多分為m個非空組，戰斗將依次進行，每回合，您的侏儒都會攻擊敵人，對每只活潑的侏儒造成一個單位的傷害，然后，敵人將向m個小組之一投擲雷電進行攻擊，閃電殺死該組中的k個地精，如果該組中的活地精少于k個，則全部殺死，當所有的侏儒都死了，戰斗就結束了，敵人將始終以最佳方式投擲雷電，以使地精造成的總傷害最小，
現在您想知道，如果以最佳方式將侏儒分為幾組，對敵人造成的最大傷害是多少？
例如，如果像在樣本輸入1中一樣，將n = 10個侏儒分為m = 4組，而雷電槍最多造成k = 3傷害，那么最佳解決方案是創建一組大的gnome，大小7和三個大小為1的小組，在第一輪中，造成10點傷害，而閃電將大組減小3，在下一輪中，造成7個傷害，大組減小為大小1，在接下來的四輪中，您分別造成4、3、2和1點傷害，每輪雷電擊中一組，總共造成10 + 7 + 4 + 3 + 2 + 1 = 27傷害，
輸入
輸入由含有三個整數n的單個線，M和K（1≤N≤10 9，1≤M，K≤10 7），其中的含義如上所述，
輸出
輸出可以對敵人造成的最大傷害，
樣例輸入 復制
10 4 3
樣例輸出 復制
27
直接上中文題意：
思路：
容易發現敵方向我方投擲的閃電所造成的傷害只有兩種型別：一種是造成k點傷害，另一種則是小于k點傷害，
然后發現所有造成k點傷害的閃電都可以歸為同一型別，
然后我們就列舉造成k點傷害的閃電的數量就行了，(小于k點傷害的閃電所造成的傷害應盡可能平均)，
具體細節見代碼：
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+15;
typedef long long ll;
int main()
{
ll n,m,k;
ll maxn=0;
cin>>n>>m>>k;
for(int h=max(ll(0),(n/k-m)-10);h<=n/k;h++)
{
/// op1 : 處理h*k所獲得的最大值.
if( (n-h*k) >= m*k )
continue;
ll maxl=n; ll minl=n-(h-1)*k; ll ld=h;
ll op1 = (maxl+minl) * ld /2;
ll yu=n-h*k;
ll v=yu/m;
ll d=yu%m;
ll temp1=( yu + (m-d)*v+v+1 ) * d /2;
ll temp2=( v + (m-d)*v ) * (m-d) /2;
ll ans= op1 + temp1+temp2;
maxn=max(maxn,ans);
}
cout<<maxn<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/48661.html
標籤：其他
上一篇：MyBatis框架之第一篇