CodeForce-812C Sagheer and Nubian Market(二分)
2024-08-30 05:42:44
Sagheer and Nubian Market
题意:n个货物,每个货物基础价格是ai。
当你一共购买k个货物时,每个货物的价格为a[i]+k*i。
每个货物只能购买一次。给你s金币,问你最多可以购买多少个货物,这些货物的最小花费。
题解:
直接二分(1~n)购买数量,每次二分都对每个货物计算价格a[i]+mid*i。
结构体对价格排序,mid个货物总价格大于s的时候break并往小二分,否则往大二分。
数据类型开long long。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
// #define _ ios::sync_with_stdio(false)
// #define cin.tie(0)
#define PI 3.141592653
using namespace std;
// #define rep(i,x,y) for(int i=x;i<y;i++)
const int INF = 10000000;
const int MAXN = 200050;
typedef long long ll; struct st
{
ll id;
ll val;
ll sum;
}a[100050];
bool cmp(st a,st b)
{
return a.sum<b.sum;
}
int main()
{
int n;
ll s;
cin>>n>>s;
for(int i=1;i<=n;i++)
{
cin>>a[i].val;
a[i].id=i;
}
int result=0;
ll t=0;
int low=0,high=n;
while(low<=high)
{
int mid=(low+high)/2;
for(int i=1;i<=n;i++)
{
a[i].sum=a[i].val+a[i].id*mid;
}
ll sm=0;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=mid;i++)
{
sm+=a[i].sum;
if(sm>s)
{break;}
}
if(sm<=s)
{
result=mid;
t=sm;
low=mid+1;
}
else
high=mid-1;
}
cout<<result<<" "<<t<<endl;
return 0;
}
最新文章
- dstoon系统中学习
- UE4 VR GUI实现 参考(UMG AND VR)
- C++ STL 迭代器失效问题
- CSS选择器及其优先级
- Q4: Two Sum
- Javascript中Array.prototype.map()详解
- 字符串匹配算法——KMP、BM、Sunday
- Oracle设计规范!
- robotframework+seleniumlibrary自动化测试:测试环境搭建
- VoIP的话音质量测量方法
- 一天搞定CSS:初识css--01
- 基于requirejs和angular搭建spa应用
- 如何在ubuntu开启ssh服务-使 SecureCRT远程登录
- 利用redis List队列简单实现秒杀 PHP代码实现
- 核心编程9 文件和文件的输入输出 (os模块)
- 20165231 预备作业二:学习基础和C语言基础调查
- SNF软件开发机器人-子系统-功能-启用大按钮样式如何配置
- redis安装--集群
- 同时使用 Ant Design of React 中 Mention 和 Form
- Hibernate学习(一)———— 第一个hibernate工程