UVALLive 7417思考
6430 ワード
UVALLive 7417タイトルリンク:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5159标题:サッカーの試合、A点1勝、B点1引き分け、C点1敗.まずnチームを与え,前mチームが昇格できることを規定した.点数は同じだが昇進できない場合がある.2つの値を聞きます:最大の昇格できない点数、最小の昇格点数.構想:伝説の大分類討論.最初の答え、すなわち(n−m)個人の1人をmに与える場合、(m+1)個人にできるだけ平均的に点数を割り当てることを考慮する.注意(m+1)個人の点数が等しくない場合、m+1人目、すなわちちょうど昇進できない人の点数の検討状況に注意すればよい.詳細はコードを参照.2番目の答えは同じです~ソース:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define LL long long
#define gmax(a,b) ((a) > (b) ? (a) : (b))
#define gmin(a,b) ((a) < (b) ? (a) : (b))
int main()
{
// freopen("J.in", "r", stdin);
int t;
scanf("%d", &t);
for(int cas = 1 ; cas <= t ; cas++){
LL n, m, a, b, c;
scanf("%lld%lld%lld%lld%lld", &n, &m, &a, &b, &c);
if(a < c)
swap(a, c);
LL ans1, ans2;
LL t1 = max(max(a, c), b) * (n - m - 1);
LL t2 = b * m;
if(a > c){
if(m % 2 != 0)
t2 = max(t2, (m - 1) / 2 * a + (m - 1) / 2 * c + max(b, c));
else
t2 = max(t2, m / 2 * a + m / 2 * c);
}
else{
if(m % 2 != 0)
t2 = max(t2, (m - 1) / 2 * c + (m - 1) / 2 * a + max(b, c));
else
t2 = max(t2, m / 2 * c + m / 2 * a);
}
// printf("t1 = %lld, t2 = %lld
", t1, t2);
ans1 = t1 + t2;
LL t3, t4;
t3 = min(min(a, c), b) * (m - 1);
t4 = b * (n - m);
if(a > c){
if((n - m) % 2 != 0)
t4 = min(t4, (n - m - 1) / 2 * a + (n - m - 1) / 2 * c + min(a, b));
else
t4 = min(t4, (n - m) / 2 * a + (n - m) / 2 * c);
}
else{
if((n - m) % 2 != 0)
t4 = min(t4, (n - m + 1) / 2 * c + (n - m - 1) / 2 * a + min(a, b));
else
t4 = min(t4, (n - m) / 2 * c + (n - m) / 2 * a);
}
// printf("t1 = %lld, t2 = %lld
", t1, t2);
// printf("t3 = %lld, t4 = %lld
", t3, t4);
ans2 = t3 + t4;
printf("Case #%d: %lld %lld
", cas, ans1, ans2);
}
return 0;
}