二分查找-CodeForces 812C-Sagheer and Nubian Market

ゞ浴缸里的玫瑰 2022-05-16 05:18 146阅读 0赞

*  # 二分查找-CodeForces 812C-Sagheer and Nubian Market #

--------------------

*  ## **题目链接：[C. Sagheer and Nubian Market][]** ##
 *  ## 思路： ##

**题目大意是有n件纪念品，一共有S元，如果买k件，那第i件纪念品的时间价格truePrice=Price+k\*i ，问在S内，最多能买多少件纪念品，如果有多种情况，选总花费最少的。**

***数据：n and S (1 ≤ n ≤ 10^5 and 1 ≤ S ≤ 10^9)*** **不出意外暴力会超时，用二分做，合法的化区间就往右走**

**然后要考虑总花费最小，定义一个优先队列，自定义greater(队头为最小价格），这样指定购买数目内可得最小总价**

*  ## 代码： ##

#include<iostream>
    #include<queue>
    #include<vector>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define MAX_SIZE 100005
    long long n,S,Consum,MinPrice=0,Max_num=0;
    long long a[MAX_SIZE];
    
    bool Judge(long long Mid)
    {
        Consum=0;
        priority_queue<long long,vector<long long>,greater<long long> > Price_List;
        for(long long i=1;i<=n;i++)
            Price_List.push(a[i]+Mid*i);
        for(long long i=0;i<Mid;i++)
        {
            Consum+=Price_List.top();
            Price_List.pop();
        }
        return Consum<=S;   //总花费不大于S
    }
    
    int main()
    {
        cin>>n>>S;
        for(long long i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        long long Left=1,Right=n,Mid;
        while(Left<=Right)
        {
            Mid=(Left+Right)/2;
            if(Judge(Mid))  //合法时记录下最大购买及最小总价
            {
                Left=Mid+1;
                MinPrice=Consum;
                Max_num=Mid;
            }
            else
                Right=Mid-1;
        }
        cout<<Max_num<<" "<<MinPrice<<endl;
        return 0;
    }

[C. Sagheer and Nubian Market]: http://codeforces.com/problemset/problem/812/C