首页 > ACM题库 > HDU-杭电 > hdu 2381 Splitting the Loot[解题报告]hoj
2014
01-05

hdu 2381 Splitting the Loot[解题报告]hoj

Splitting the Loot

问题描述 :

After a lucrative enterprise (the details of which are best left untold) a large gold bar has come into your possession. However, since you promised your accomplices a share of the loot, you will need to split it up into several pieces.

Dividing a gold bar is not an easy task. Fortunately, you’ve found a goldsmith willing to do it without asking questions, under the conditions that he can keep a fixed percentage of the bar being divided as payment for his labour, and he will only divide it into two parts (although they don’t have to be equal halves; you can pick the ratio).

For example, suppose you have a 100 gram gold bar, you have promised your two accom- plices a share of 15 and 21 gram respectively and the goldsmith asks a 10% fee for each split. You can then first split the bar at a ratio of 5:4, yielding a 50 gram part (which you keep) and a 40 gram piece, which you split at 5:7 to yield the 15 and 21 gram pieces for your accomplices. Note that at each cut, you lose 10% of the gold to the goldsmith.

Since you want to maximize your own share of the loot without being unfair to your accomplices, you must be careful in the way you divide up the gold. In the example, if you had started by cutting off a 15 gram piece first, and then a 21 gram piece off the remaining bar, you would have ended up with only a 46.5 gram piece for yourself.

Your task is to determine how much gold you can keep, if you make the right cuts!

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

A line with three integers: the weight of the gold bar w (1 <= w <= 1 000 000), the cutting fee as a percentage p (0 <= p < 100), and the number of accomplices n (1 <= n <= 50).

n lines, each with the integer share s (1 <= s <= w) you promised an accomplice.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

A line with three integers: the weight of the gold bar w (1 <= w <= 1 000 000), the cutting fee as a percentage p (0 <= p < 100), and the number of accomplices n (1 <= n <= 50).

n lines, each with the integer share s (1 <= s <= w) you promised an accomplice.

样例输入:

3
100 10 2
15
21
45 15 3
11
11
11
50 0 3
10
20
25

样例输出:

50
0
-1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>
#include <sstream>
#include <string>
using namespace std;
#define out(X) cerr << #X << ": " << (X) << endl
#define SZ(X) ((int)(X.size()))
#define LENGTH(X) ((int)(X.length()))
#define REP(I,N) for (int I = 0; I < (N); ++I)
#define FOR(I,L,H) for (int I = (L); I < (H); ++I)
#define MP(X,Y) make_pair((X),(Y))
#define PB push_back
#define ALL(X) X.begin(), X.end()
template <typename T> inline bool checkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline bool checkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long lint;

const double EPS = 1e-9;
int sgn(const double &x) {return (int)((x > EPS) - (x < -EPS));}

int T,N;
double tot,p;
vector<double> bef,aft,init;

int check(const double &mid) {
 bef.clear();
 aft.clear();
 for(int i = 0 ; i < N ; i++) {
 bef.push_back(init[i]);
 }
 if (sgn(mid) != 0) bef.push_back(mid);
 while(SZ(bef) > 1) {
 sort(ALL(bef));
 aft.clear();
 aft.push_back((bef[0] + bef[1]) / (1 - p));
 for(int i = 2 ; i < SZ(bef) ; i++) {
 aft.push_back(bef[i]);
 }
 bef = aft;
 }
 if (sgn(bef[0] - tot) > 0) {
 return -1;
 }
 return 1;
}

int main() {
 
 scanf("%d",&T);
 while(scanf("%lf%lf%d",&tot,&p,&N) == 3) {
 p /= 100.0;
 init.clear();
 for(int i = 0 ; i < N ; i++) {
 double w;
 scanf("%lf",&w);
 init.push_back(w);
 }
 
 double ans = -1;
 double l = 0.0 ,r = tot,mid;
 for(int cnt = 0 ; cnt < 200 ; cnt++){
 mid = (l + r) / 2;
 if (check(mid) != -1) {
 l = mid + EPS;
 ans = mid;
 }
 else r = mid - EPS;
 }
 if (sgn(ans + 1) <= 0) {
 printf("%d\n",-1);
 continue;
 }
 printf("%.4f\n", ans); 
 }

 return 0;
}

  1. 是穷举,但是代码有优化(v数组),并不是2^n。测试数据应该没问题,之前有超时的代码。

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。