当前位置: 首页 > news >正文

武汉网站制作多少钱湖南 seo

武汉网站制作多少钱,湖南 seo,上海高端室内设计,ebay网站做外贸优缺点一、题目大意 题目中给出了N头牛,这些牛要互相叠罗汉,牛i承担的风险risk[i]为牛i上面的牛的质量之和sum[i](如果上面没有牛就是0)减去牛i的力量strength[i],即risk[i]sum[i]-strength[i] 我们要优化这个叠罗汉的顺序…

一、题目大意

题目中给出了N头牛,这些牛要互相叠罗汉,牛i承担的风险risk[i]为牛i上面的牛的质量之和sum[i](如果上面没有牛就是0)减去牛i的力量strength[i],即risk[i]=sum[i]-strength[i]

我们要优化这个叠罗汉的顺序,使得1-N头牛的风险值中的最大值,最小。

二、解题思路

这个题目要对风险值进行二分

首先我们设牛i的质量为weight[i],牛i的力量为strength[i],风险值为mid,所有牛的质量之和为sum,按叠罗汉顺序从下往上数最底下一头牛为first,倒数第二头牛为second,第三个为third,那么有如下表达式。

sum-weight[first]-strength[first]<=mid
sum-weight[first]-weight[second]-strength[second]<=mid
sum-weight[first]-weight[second]-weight[third]-strength[third]<=mid

不难看出,我们让顺序靠下的牛在满足条件的情况下,质量尽可能大,那么就缓解了顺序靠上的牛的压力。

所以题目对风险值进行二分,然后判断风险值是否可行,如果可行,则缩小风险值,如果不可行,则放大风险值,输出最后一次满足条件的风险值即可。

判断的过程的思路来自于上面的表达式,如果我们让底下的牛的质量尽可能大,那么对顶上的牛的力量的要求就不会那么严苛。判断过程中进行N次循环,每次找到满足 当前剩余牛的重量-牛i的重量-牛i的力量<=mid 条件的所有牛i,放入到优先队列中,取出质量最大的放在底下,同时更新剩余牛的重量,然后继续下次循环,如果优先队列为空了,那么代表我们找不到满足条件的牛i,则mid过小,返回false,N次循环正常结束,则mid可行。(需要注意的是要避免优先队列放入重复的元素)

三、代码

代码这里为了防止中途计算溢出,对mid开了一个long long,对于本题目的数据其实可以不开。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
struct Cow
{int weight, strength;Cow(int weight = 0, int strength = 0) : weight(weight), strength(strength) {}
};
int N;
Cow cows[50007];
int inf = 0x3f3f3f3f, weightSum = 0;
bool operator<(const Cow &a, const Cow &b)
{return a.weight < b.weight;
}
bool compare(const Cow &a, const Cow &b)
{return (a.strength + a.weight) < (b.strength + b.weight);
}
void input()
{scanf("%d", &N);for (int i = 0; i < N; i++){scanf("%d%d", &cows[i].weight, &cows[i].strength);weightSum += cows[i].weight;}sort(cows, cows + N, compare);cows[N] = Cow(0, inf);
}
// 判断最小风险mid是否可行
bool judge(int mid)
{priority_queue<Cow> que;int right = N, currentSum = weightSum;for (int i = 0; i < N; i++){int next = lower_bound(cows, cows + N + 1, Cow(currentSum - mid, 0), compare) - cows;for (int j = next; j < right; j++){que.push(cows[j]);}right = next;if (que.empty()){return false;}Cow cow = que.top();que.pop();currentSum -= cow.weight;}return true;
}
void binarySearch()
{int left = -1000000001, right = weightSum;while (left + 1 < right){ll mid = left;mid += right;mid = mid >> 1;if (judge((int)mid)){right = (int)mid;}else{left = (int)mid;}}printf("%d\n", right);
}
int main()
{input();binarySearch();return 0;
}

http://www.ritt.cn/news/22049.html

相关文章:

  • wordpress建个人网站如何设置友情链接
  • 给小孩子做网站百度知道入口
  • 文化传播集团网站建设网络营销方案策划案例
  • 网站底部样式百度权重1
  • 现代化专业群建设网站某网站搜索引擎优化
  • 学习建站的网站夫唯老师seo
  • 广州红盾信息门户网站东莞seo建站如何推广
  • 网站制作网站开发ple id充值百度交易平台官网
  • 椒江网站制作网站建设策划书
  • 重庆南岸营销型网站建设公司推荐seo产品优化免费软件
  • 个人软件外包接单平台宁波网站制作优化服务公司
  • 华为云域名注册seo学徒
  • 关于做花茶网站的策划书网站查询域名入口
  • 嘉兴高端网站建设有限公司女装关键词排名
  • 网站建设网站自助建设信息流优化师工作内容
  • 网络安全网站游戏广告联盟平台
  • qq推广开通南宁百度seo推广
  • 58同城青岛网站建设新冠疫情最新消息
  • 国外经典手机网站设计东莞百度推广排名
  • 江西头条新闻今天seo技术培训沈阳
  • 湛江专门做网站今日新闻头条最新消息
  • 网站内部资源推广牛排seo系统
  • qq怎么做自己的网站seo是什么职务
  • 网站建设和seo的工作好不好安阳企业网站优化外包
  • 网站建设价钱最新疫情最新消息
  • 高端html5网站建设织梦模板营业推广的目标通常是
  • 湖南的商城网站建设关键词seo价格
  • 长沙 网站开发报价排名优化哪家专业
  • 网站后台登陆路径登封网络推广公司
  • wordpress禁用谷歌的插件合肥网站seo整站优化