洛谷题单指南-贪心-P1080 [NOIP2012 提高组] 国王游戏

标签：10 NOIP2012 int 洛谷题 back vector P1080 res size

原题链接：https://www.luogu.com.cn/problem/P1080

题意解读：通过不同的排队方式，让获得最多奖赏的大臣金额尽可能的少。此题如果没有思路，用全排列枚举可以“骗”分，更好的做法直觉上是某种贪心策略，另外基于数据规模考虑，要拿满分，需要上高精度。下面就由浅入深一步一步的解决。

解题思路：

1、枚举排列

观察数据，前20%的数据量级在10以内，如果用全排列暴力枚举，复杂度在10!*10*10以内，能得多少分就听天由命。

全排列可以借助next_permuation函数，也可以自行dfs

20分代码：

#include <bits/stdc++.h>
using namespace std;

int n;
pair<int, int> a[1005];
long long ans = LLONG_MAX;

int main()
{
    cin >> n;
    for(int i = 0; i <= n; i++) cin >> a[i].first >> a[i].second;

    vector<int> v;
    for(int i = 1; i <= n; i++) v.push_back(i); //初始排列
   
    do 
    {
        long long t = a[0].first; //初始乘积是国王左手数字
        long long maxx = 0;
        for(auto i : v)
        {
            maxx = max(maxx, t / a[i].second); //计算每一个人获得的奖励
            t = t * a[i].first; //乘积乘上当前左手的数，便于计算下一个人的奖励
        }
        ans = min(ans, maxx);

    } while(next_permutation(v.begin(), v.end()));

    cout << ans;

    return 0;
}

2、贪心策略-1

由于要得到获得最大金币数的人，

而对于每一个人，要想获得最大金币数，必须排在最后一个位置

证明：对于一个人左手a、右手b，排在前面的所有人左手乘积是t，其获得的金币数为t / b

要使得金币数越大，t自然是越大越好，排名越靠后，t越大

因此，对于每一个人，其能获得的最大金币数为 T / (a * b)，T表示所有人左手数字乘积

那么只需要找到能获得的最大金币数中最小值即可

50分代码：

#include <bits/stdc++.h>
using namespace std;

int n;
pair<int, int> a[1005];
long long ans = LLONG_MAX;
long long t = 1;

int main()
{
    cin >> n;
    for(int i = 0; i <= n; i++)
    {
        cin >> a[i].first >> a[i].second;
        t *= a[i].first;
    } 

    for(int i = 1; i <= n; i++)
    {
        long long res = t / (a[i].first * a[i].second);
        if(res > 0) ans = min(ans, res); //res>0是因为如果大臣最多获得金币是0，不参与比较
    }

    cout << ans;
    
    return 0;
}

接下来的问题，就是要把计算乘法、除法的地方替换成高精度，主要会用到高精度*低精度，高精度➗低精度

在“模拟与高精度”模块中已多次介绍，不再具体讲述其实现原理。

90分代码：

#include <bits/stdc++.h>
using namespace std;

int n;
pair<int, int> a[1005];
vector<int> ans(4005, 9); //1≤n≤1,000,0<a,b<10000, 所有a乘积长度在4000左右，定义一个最大值
vector<int> t(1, 1); //所有左手数的乘积

vector<int> mul(vector<int> &a, int b)
{
    vector<int> res;

    int t = 0;
    for(int i = 0; i < a.size(); i++)
    {
        t += a[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }

    while(t)
    {
        res.push_back(t % 10);
        t /= 10;
    }

    return res;
}

vector<int> div(vector<int> &a, int b)
{
    vector<int> res; 
    int r = 0;
    for(int i = a.size() - 1; i >= 0; i--)
    {
        r = 10 * r + a[i];
        if(r >= b)
        {
            res.push_back(r / b);
            r %= b;
        }
        else res.push_back(0);
    }

    //将res翻转过来，统一低位在前的方式
    vector<int> res2; 
    for(int i = res.size() - 1; i >= 0; i--)
    {
        res2.push_back(res[i]);
    }

    //去除前导0
    while(res2.back() == 0 && res2.size() > 1) res2.pop_back();

    return res2;
}

//a > b返回正数，a = b返回0， a < b返回负数
int compare(vector<int> &a, vector<int> &b)
{
    if(a.size() != b.size()) return a.size() - b.size();
    else
    {
        for(int i = a.size() - 1; i >= 0; i--)
        {
            if(a[i] != b[i]) return a[i] - b[i];
        }
        return 0;
    }   
}

int main()
{
    cin >> n;
    for(int i = 0; i <= n; i++)
    {
        cin >> a[i].first >> a[i].second;
        t = mul(t, a[i].first);
    } 

    for(int i = 1; i <= n; i++)
    {
        vector<int> res = div(t, a[i].first * a[i].second);
        if(compare(ans, res) > 0) ans = res;
    }

    for(int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
    
    return 0;
}

3、贪心策略-2

以上方法为什么只能得到90分？

原因在于此方法无法处理左手数全是1的情况，这样每个人排最后不一定代表这种排序方式的最大值，因为有可能右手数大于1，这样获得金币为0

前面如果有一个右手数是1的，获得金币为1，这才是最大值。

举例：

在以上策略下输出是0，真实结果应该是1。

换一种思路，设第i、j两个人，i、j连续，i左手a[i].l、右手a[i].r，j左手a[j].l、右手a[j].r

如果i在j前面，对最终答案的影响值是a[i].l / a[j].r

如果j在i前面，对最终答案的影响值是a[j].l / a[i].r

要保持i在j前面，必须a[i].l / a[j].r < a[j].l / a[i].r

有a[i].l * a[i].r < a[j].l * a[j].r

因此得知，一个人排在前面，必须左右手乘积更小，这样答案才会更小。

所以，只需要对每个大臣按左右手乘积从小到大排序，再计算最大的金币即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

struct p
{
    int l ,r;
} a[1005];

bool cmp(p p1, p p2)
{
    return p1.l * p1.r < p2.l * p2.r;
}

int n;
vector<int> ans(1, 0); 
vector<int> t(1, 1);

vector<int> mul(vector<int> &a, int b)
{
    vector<int> res;

    int t = 0;
    for(int i = 0; i < a.size(); i++)
    {
        t += a[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }

    while(t)
    {
        res.push_back(t % 10);
        t /= 10;
    }

    return res;
}

vector<int> div(vector<int> &a, int b)
{
    vector<int> res; 
    int r = 0;
    for(int i = a.size() - 1; i >= 0; i--)
    {
        r = 10 * r + a[i];
        if(r >= b)
        {
            res.push_back(r / b);
            r %= b;
        }
        else res.push_back(0);
    }

    //将res翻转过来，统一低位在前的方式
    vector<int> res2; 
    for(int i = res.size() - 1; i >= 0; i--)
    {
        res2.push_back(res[i]);
    }

    //去除前导0
    while(res2.back() == 0 && res2.size() > 1) res2.pop_back();

    return res2;
}

//a > b返回正数，a = b返回0， a < b返回负数
int compare(vector<int> &a, vector<int> &b)
{
    if(a.size() != b.size()) return a.size() - b.size();
    else
    {
        for(int i = a.size() - 1; i >= 0; i--)
        {
            if(a[i] != b[i]) return a[i] - b[i];
        }
        return 0;
    }   
}

int main()
{
    cin >> n;
    for(int i = 0; i <= n; i++)
    {
        cin >> a[i].l >> a[i].r;
    } 

    sort(a + 1, a + n + 1, cmp);

    t = mul(t, a[0].l); //国王的左手值
    for(int i = 1; i <= n; i++)
    {
        vector<int> res = div(t, a[i].r); //计算当前人活得的金额
        if(compare(ans, res) < 0) ans = res; //更新最大值
        t = mul(t, a[i].l); //t乘以当前人左手数，便于计算下一个
    }

    for(int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
    
    return 0;
}

标签：10,NOIP2012,int,洛谷题,back,vector,P1080,res,size
From： https://www.cnblogs.com/jcwy/p/18037102

洛谷题单指南-贪心-P1080 [NOIP2012 提高组] 国王游戏

相关文章

赞助商

阅读排行