时间戳

首页 > 技术文章 > Offer收割_5

Offer收割_5

luntai 2016-08-15 10:54 原文

训练 投入 欲望。  ---贾森博尔特

第一题：二分枚举答案，check时候模拟一下即可。

　　　　时间复杂度： O(n*logn)。

第二题：

描述

小Hi在虚拟世界中有一只小宠物小P。小P有K种属性，每种属性的初始值为Ai。小Ho送给了小Hi若干颗药丸，每颗药丸可以提高小P指定属性1点。通过属性值，我们可以计算小P的强力值=(C1(1/B1))*(C2(1/B2))*...*(CK(1/BK))，其中Ci为小P第i项属性的最终值（Ai+药丸增加的属性）。 已知小Ho送给小Hi的药丸一共有N颗，问小P的强力值最高能够达到多少？

输入

第一行包含两个整数N，K，分别表示药丸数和属性种数。

第二行为K个整数A1 - AK，意义如前文所述。

第三行为K个整数B1 - BK，意义如前文所述。

对于30%的数据，满足1<=N<=10, 1<=K<=3

对于100%的数据，满足1<=N<=100000, 1<=K<=10

对于100%的数据，满足1<=Ai<=100, 1<=Bi<=10

输出

输出小P能够达到的最高的强力值。

只要你的结果与正确答案之间的相对或绝对误差不超过千分之一，都被视为正确的输出。

样例输入

5 2
1 1
3 2

样例输出

2.88

解体思路：

1.一开始yy的各种结论，发现不准。最后，为了搞定小数据集，暴力将n分解成k份，然后求解。这样可以过掉30%的小数据。

//
//  main.cpp
//  ProjectC
//
//  Created by LiJinxu on 16/8/13.
//  Copyright © 2016年 LiJinxu-NEU. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int Maxn = 100001;
int n, k;
double a[Maxn], b[Maxn];
vector<pair<double, double>>rec;

bool cmp(pair<double, double> &p1, pair<double, double> &p2){
    if(p1.first == p2.first){
        return p1.second < p2.second;
    }
    return p1.first < p2.first;
}

void divideN2Kparts(int pos, int left, int *path, vector<vector<int>>&rec)
{
    if(left == 0 && pos == k){
        vector<int>tmp;
        for(int i = 0; i < k; i ++)
            tmp.push_back(path[i]);
        rec.push_back(tmp);
        return ;
        
    }else if(left && pos >= k){
        return ;
    }
    for(int i = n; i >= 0; i --){
        if(left < i) continue;
        left -= i;
        path[pos] = i;
        pos ++;
        divideN2Kparts(pos, left, path, rec);
        pos --;
        path[pos] = 0;
        left += i;
    }
}

void smallSolution()
{
    vector<vector<int>>rec;
    int path[Maxn];
    for(int i = 0;i < k; i ++)
        path[i] = 0;
    divideN2Kparts(0, n, path, rec);
    double fAns = 0;
    for(int i = 0; i < rec.size(); i ++){
        double ans = 1;
        for (int j = 0; j < rec[i].size(); j++) {
            ans *= pow(a[j] + (double) rec[i][j], (1.0/b[j]));
        }
        if(fAns < ans)
            fAns = ans;
    }
    printf("%.2lf\n",fAns);

}
int main() {
    cin>>n>>k;
    for(int i = 0; i < k; i ++){
        scanf("%lf", &a[i]);
    }for(int i = 0; i < k; i ++)
        scanf("%lf", &b[i]);
    smallSolution();
    return 0;
}

2.全解方案：

　　根据题意强力值P=(C1(1/B1))*(C2(1/B2))*...*(CK(1/BK)), Ci = (Ai + Xi), N = X0 + .. + Xk; 目标是：让P最大。因为是乘法求最大值问题，我们通过两边去对数log得到：

　　logP = （1/B1）logC1 + (1/Bi)logCi + (1/Bk)logCk 。 Ci = Ai + Xi。 这样，为了使P最大，我们只需要每次增量（△x = 1）使得整体增量最大即可：max(1/Bi * log(Ai + 1) - 1/Bi * log(Ai))。因为每次增加1，也就是增加到C1 - Ck中的某一项，使得增益最大即可。这里就能够体现出加法的好处，易于衡量结果。 

　　最后，只需要使用一个数据结构（priority_queue）来动态维护每次给对应项增加1(满足收益最大)的过程就好了。 时间复杂度：O(n*logn);

　　这道题的关键是：增量为1，1个1个的考虑，而不是像我开始解决小规模数据集的思路，上来直接把n分成k份这样整体考虑。k在[1,10]很小，用优先队列维护开销不大。

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>
#include <vector>
#include <map>
#define INF 0x3f3f3f3f

using namespace std;

const int Maxn = 100001;
int n, k;
double a[Maxn];
struct node{
    double x, y;
    int id;
    bool operator <(const node &p)const{
        return 1.0 / y * (log(x + 1) - log(x)) < 1.0 / p.y * (log(p.x + 1) - log(p.x));
    }
}rec[Maxn];

priority_queue<node>p_que;

int main()
{
    cin>>n>>k;
    for(int i = 0; i < k; i ++){
        scanf("%lf", &a[i]);
        rec[i].x = a[i];
        rec[i].id = i;
    }
    for(int i = 0; i < k; i ++)
        scanf("%lf", &rec[i].y);
    for(int i = 0; i < k; i ++)
        p_que.push(rec[i]);
    for(int i = 0; i < n; i ++){
        node p = p_que.top();
        p_que.pop();
        p.x ++;
        a[p.id] ++;
        p_que.push(p);
    }
    double ans = 1.0;
    for(int i = 0; i < k; i ++){
        ans *= pow(a[i], 1.0/rec[i].y);
    }
    printf("%lf\n",ans);
    //system("pause");
    return 0;
}

　　最后，关于优先队列的运算符重载，只能重载<。其他运算符会出错。return x > a.x //x小的在前。return x < a.x //x大的在前。

 

推荐阅读