Sagheer and Nubian Market

CodeForces - 812C

题意: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;
}

最新文章

  1. dstoon系统中学习
  2. UE4 VR GUI实现 参考(UMG AND VR)
  3. C++ STL 迭代器失效问题
  4. CSS选择器及其优先级
  5. Q4: Two Sum
  6. Javascript中Array.prototype.map()详解
  7. 字符串匹配算法——KMP、BM、Sunday
  8. Oracle设计规范!
  9. robotframework+seleniumlibrary自动化测试:测试环境搭建
  10. VoIP的话音质量测量方法
  11. 一天搞定CSS:初识css--01
  12. 基于requirejs和angular搭建spa应用
  13. 如何在ubuntu开启ssh服务-使 SecureCRT远程登录
  14. 利用redis List队列简单实现秒杀 PHP代码实现
  15. 核心编程9 文件和文件的输入输出 (os模块)
  16. 20165231 预备作业二:学习基础和C语言基础调查
  17. SNF软件开发机器人-子系统-功能-启用大按钮样式如何配置
  18. redis安装--集群
  19. 同时使用 Ant Design of React 中 Mention 和 Form
  20. Hibernate学习(一)———— 第一个hibernate工程

热门文章

  1. MyBatis学习06(动态SQL和缓存)
  2. JVM学习笔记-第七章-虚拟机类加载机制
  3. Sqli-Labs less26-28a
  4. noip37
  5. NOIP 模拟 10 考试总结
  6. MVVMLight学习笔记(六)---DispatchHelper更新UI
  7. spring学习日志四
  8. jQuery mobile网格布局
  9. jquery mobile常用的data-role类型
  10. python常用工具库介绍