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

03 P1314 [NOIP2011 提高组] 聪明的质监员

题目:

代码:

#include<iostream>
using namespace std;int sa[125][125];/*
二分思想:
s=0,全计算,y大,且s小,所以不行
s=oo ,全不过,y小,但s大,所以不行于是我们取mid,根据结果取区间前缀和思想:
求w的价值之和时
*/#define M 200005
int v[M];
int w[M];
int l[M];
int r[M];
long long pre_n[M],pre_v[M];
long long Y,s,sum;
int n,m,mx=-1,mn=2147483647;//给标准s,计算y(每个标准都有一个y)
bool check(int W)
{for(int i=1;i<=n;i++){//计算yi//大于标准,计算if(w[i]>W){//本项结果为1,上一项为n[i-1],同时完成了前缀和和传入的任务pre_n[i]=pre_n[i-1]+1;pre_v[i]=pre_v[i-1]+v[i];}//小于标准,忽略else{pre_n[i]=pre_n[i-1];pre_v[i]=pre_v[i-1];}}//计算s(前缀和使用)for(int i=1;i<=m;i++){//每一个yi对应了pre——n和pre——v这两个前缀和Y+=(pre_n[r[i]]-pre_n[l[i]-1])*(pre_v[r[i]]-pre_v[l[i]-1]);}//在下面每有一次循环就算一次,传到全局sum=llabs(Y-s);//用于二分if(Y>s){return 1;    }else{return 0;}}int main()
{//n为矿石数目,m为区间数目,s为重量标准int n,m,s;cin>>n>>m>>s;//v和w分别输入for(int i=1;i<=n;i++){cin>>v[i]>>w[i];//记录最值,方便二分mx=max(w[i],mx);mn=min(w[i],mx);}for(int i=1;i<=m;i++){//存储区间cin>>l[i]>>r[i];}//s的上下界int left=mn-1;int right=mx+2;int mid;long long ans=0x3f3f3f3f3f3f3f3f;//二分查找while(left<right){//相当于除以二,防止left+right太大导致崩溃mid=(left+right)/2;//循环二分查找,当mid为标准时//用sum传出目标,从而计算最小值//返回左右关系,从而修改二分区间//传回左右关系if(check(mid)){left=mid+1;}else{right=mid-1;}//传回大小if(sum<ans){ans=sum;}}cout<<ans<<endl;}


http://www.mrgr.cn/news/74889.html

相关文章:

  • 免费,WPS Office教育考试专用版
  • 基于微信小程序的乡村研学游平台设计与实现,LW+源码+讲解
  • 随手记:简单实现纯前端文件导出(XLSX)
  • Scaling Laws终结,量化无用,AI大佬都在审视这篇论文
  • 数据结构-串
  • 在 Service Worker 中caches.put() 和 caches.add()/caches.addAll() 方法他们之间的区别
  • 群控系统服务端开发模式-应用开发-前端角色功能开发
  • AI界盛会来袭!高录用EI会议(IS-AII 2025)你绝不能错过!
  • 【B+树特点】
  • Aippyy如何写论文?ai人工智能写作哪家好?
  • java项目-jenkins任务的创建和执行
  • DasViewer可以批量加载osgb格式文件吗?
  • C++初阶:类和对象(上)
  • Fiddler安装配置+抓包手机
  • Javascript 判断数据类型
  • IDEA中创建多模块项目步骤
  • 【2025国考|考公资料】轻松备考:你的公职考试全攻略,快速提升通过率!
  • 【实战场景】企业敏感词拦截如何实现?怎么避免员工发送违规词?这个方法大可一试!
  • 原型设计救星降临:深度解析5款超燃原型工具
  • 高端定制网站是什么样的?推荐几家优质网站建设公司!
  • [【comfyui教程】ComfyUI]Flux:非常好用的自定义多区域提示插件,精确绘图,多风格融合出图!
  • qt QCamera详解
  • Kafka节点服役和退役
  • 算法——移除链表元素(leetcode203)
  • 单片机设计电流与温度监控python上位机监控平台设计
  • 三维点云 和模型转换的问题