题目链接:https://zhixincode.com/contest/18/problem/I?problem_id=267
题目描述
输入描述
输出描述
一行一个整数表示答案。
样例输入 1
3
20 1
15 10
20 2
样例输出 1
60
题解:
首先肯定的是,这 $n$ 次选择必然是分为两段的,前一段全部是召唤,后一段全部是加攻。
然后我们只需要考虑,这两段的数目即可,然后我们假设这个函数和最后的总攻击力是一个单峰函数,就可以上三分。
那么接下来考虑在确定多少张牌召唤,多少张牌加攻的前提下,怎么安排顺序:
因为生物数目是确定的 $x$,所以我们可以知道一张牌它如果 $b \cdot x - a$ 越大,把它选成加攻击力就更赚,因此可以排个序后确定哪些牌是召唤、哪些牌是加攻,从而最终确定总攻击力。
最后的时间复杂度就是 $O(\log_{1.5}n \cdot n \cdot \log_{2} n)$。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a(p) (p.first)
#define b(p) (p.second)
const int maxn=1e5+; int n,x;
P c[maxn];
inline bool cmp(const P& u,const P& v) {
return b(u)*x-a(u)<b(v)*x-a(v);
}
ll check(int mid)
{
x=mid, sort(c+,c+n+,cmp);
ll res=;
for(int i=;i<=n;i++) res+=(i<=x)?a(c[i]):b(c[i])*x;
return res;
} int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n;
for(int i=;i<=n;i++) cin>>a(c[i])>>b(c[i]);
int l=, r=n; ll ans=;
while(l<=r)
{
if(r-l<=)
{
for(int i=l;i<=r;i++) ans=max(ans,check(i));
break;
}
int lmid=l+(r-l)/, rmid=l+(r-l)*/;
ll lres=check(lmid), rres=check(rmid);
if(lres<=rres) l=lmid;
else r=rmid;
}
cout<<ans<<endl;
}