有没有专门做团购的网站,成都短视频制作培训班,莱芜新闻最新消息,商城网站建设相关费用Sagheer and Nubian Market CodeForces - 812C 题意#xff1a;n个货物#xff0c;每个货物基础价格是ai。 当你一共购买k个货物时#xff0c;每个货物的价格为a[i]k*i。 每个货物只能购买一次。给你s金币#xff0c;问你最多可以购买多少个货物#xff0c;这些货物的最小… 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 ix;iy;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.sumb.sum;
}
int main()
{int n;ll s;cinns;for(int i1;in;i){cina[i].val;a[i].idi;}int result0;ll t0;int low0,highn;while(lowhigh){int mid(lowhigh)/2;for(int i1;in;i){a[i].suma[i].vala[i].id*mid;}ll sm0;sort(a1,a1n,cmp);for(int i1;imid;i){sma[i].sum;if(sms){break;}}if(sms){resultmid;tsm;lowmid1;}else highmid-1;}coutresult tendl;return 0;
} 转载于:https://www.cnblogs.com/YingZhixin/p/7133149.html
