1044 Shopping in Mars
这题我写了两个二分函数。
BS借用的模板是找到第一个大于等于总价的商品下标，然后返回的是钻石价值和减去商品总价，通过遍历来得到最小的差值，注意遍历的最后一个数字的时候可能会返回负值，所以只有当返回值大于等于0才可以用来竞争最小差值。
得到了最小差值。BS2函数的模板是找到符合固定条件的商品下标，当然可能找不到，此时返回-1。
AC代码
#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<map>using namespace std;const int SUP = 100000000;
const int maxn = 100010;vector<pair<int,int> > ans;
int n,T;
int M[maxn];
int C[maxn];int getT(int begin,int end){return C[end]-C[begin]+M[begin];
}int BS(int begin,int l,int r){int mid,dif;while(l<r){mid = (l+r)/2;if(getT(begin,mid)>=T){r = mid;}else{l = mid+1;}}dif = getT(begin,l) - T;return dif;
} int BS2(int begin,int l,int r,int dif){int mid;while(l<=r){mid = (l+r)/2;if(getT(begin,mid)<T+dif){l = mid+1;}else if(getT(begin,mid)>T+dif){r = mid-1;}else return mid;}return -1;
}int main(){cin>>n>>T;C[0] = 0;for(int i=1;i<=n;i++){cin>>M[i];C[i] = C[i-1]+M[i];}int minDif = SUP;for(int i=1;i<=n;i++){int dif = BS(i,i,n);if(dif>=0){minDif = min(minDif,dif);}}
// printf("minDif = %d\n",minDif); for(int i=1;i<=n;i++){int j = BS2(i,i,n,minDif);if(j!=-1)printf("%d-%d\n",i,j);}return 0;
}相关文章：
nodeJS之eventproxy源码解读
1.源码缩影 !(function (name, definition) { var hasDefine typeof define function, //检查上下文环境是否为AMD或CMD hasExports typeof module ! undefined && module.exports; //检查上下文环境是否为Node if (hasDefine) { define(definition); //AMD环境或CM…
解决phpmyadmin3.4空密码登录被禁止登陆的方法
很多时候我们在本机测试时会将root用户密码设置为空。因为我把php升级到了5.3.1，以前的phpmyadmin版本不能用了，就升级到phpMyAdmin 3.2.4版的时候，会遇到无法以空密码登录root用户的情况。怎么解决呢? 请参照如下步骤： 1、打开程…
CentOS安装新版RabbitMQ解决Erlang 19.3版本依赖
2019独角兽企业重金招聘Python工程师标准>>> 通过yum等软件仓库都可以直接安装RabbitMQ，但版本一般都较为保守。 RabbitMQ官网提供了新版的rpm包（http://www.rabbitmq.com/download.html），但是安装的时候会提示需要erl…
1048 Find Coins(二分法解法)
非常基础的二分法-寻找序列中是否存在某一条件的元素 的应用 AC代码 #include<cstdio> #include<iostream> #include<set> #include<vector> #include<map> #include<algorithm>using namespace std;const int SUP 100000000; const in…
关于chrome等浏览器不支持showModalDialog的解决方案
目前，新版本的chrome和opera、Firefox等浏览器已经不支持showModalDialog方法。 如果是没有接收返回值的，可以直接将window.showModalDialog改为window.open。 需要接收返回值的情况： 父页面设置： var uIdName; function chooseus…
Flex Javascript 交互实现代码
关键字：ExternalInterface所用类库：SWFObject/*** Flex调用Javascript函数* params functionName:String Javascript函数名称* params ...params Javascript函数参数* return 返回Javascript函数的return内容**/ExternalInterface.call(functionName:Str…
C#反射使用时注意BindingFlags的用法（转载）
最近刚刚开始用反射做项目，遇到一个小的知识点，记录一下。 c#反射查找方法时，默认只能查到public方法。如果想要查找private方法，需要设定BindingFlags. 即： BindingFlags.Public|BindingFlags.Instance 默认…
1126 Eulerian Path
主要考英语或者数学基础。 一幅连通图的奇点个数为0或2时才能够被一笔画。 连通图的判断用DFS来计数。 连通图0个奇点：Eulerian 连通图2个奇点：semi-Eulerian 非连通图/连通图其他数量的奇点：non-Eulerian AC代码 #include<cstdio&…
各种小的 dp （精）
Q~ 抛一枚硬币 n 次，每次可能是正面或者反面向上，求没有连续超过 k 次硬币向上的方案数 A ： dp[ i ] 表示到 i 位置的方案数， 1 . 当 i < k 时， dp[i] dp[i-1]*2 2 . 当 i k 时， dp[i] dp[i-1]*2 - 1…
写给还在大学的兄弟姐妹
看到软件专业毕业生之一个月攻略 这篇文章之后，忽然想起了自己两个多月前找工作时的写的一篇文章，便拿出来与大家分享。这仅是个人的一些看法，不正确之处还请各位指出，有砖尽管拍。 基础很重要 许多企业招聘，要求大学…
grunt学习
1、http://javascript.ruanyifeng.com/tool/grunt.html Grunt：任务自动管理工具 2、转载于:https://www.cnblogs.com/king-bj/p/4322794.html
IP地址和MAC地址
MAC地址又称硬件地址，是MAC帧的头部，在数据链路层只能看见MAC地址。 IP地址是逻辑地址，是IP数据报的头部，路由器根据IP地址进行路由选择。 IP地址为4个字节32位，编制经历了3个历史阶段。 MAC地址为6个字节48位。
ie9下console不兼容的问题
最近在调整项目在ie9下的展示问题，发现在ie9下，js文件不执行，打开控制台才执行，原因是ie9不支持console，以下给出两种解决方案：1. 在webpack.prod.conf.js 中添加并修改js插件配置项（我用的是we…
[转载] linux、Solaris下xdmcp远程桌面服务
原文链接 http://youlvconglin.blog.163.com/blog/static/52320420106243857254/ 使用图形界面远程登录linux和Solaris，首先要在服务端开启xdmcp服务，windows下使用xmanager连接 Ubuntu下则使用下默认也安装了该客户端，一次打开[应用程序]-[…
3.2.4 控制图层显示的范围
为了是地图更加简洁 和 减小地图负载 ，达到分级显示某些图层的效果，应该为每一个图层设置 合理的 可见比例尺范围。1 begin2 3 aeMapMain.Layer[2].MaximumScale :500000;//最大可见比例尺 分母4 aeMapMain.Layer[2].MinimumScale :1000000;//最小可见比…
1103 Integer Factorization 需再做
本题是典型的DFS剪枝 我对DFS有了更深的认识：整个过程就是一片森林(根节点不唯一)的生长，到了界限就得到结果并返回或者得不到结果也返回，DFS的参数存放的是所有需要积累的变量。 提示： 1. 最外层的while或者for可以看成是一个…
POJ1001--Exponentiation（幂计算）翻译
Exponentiation幂计算Time Limit: 500MSMemory Limit: 10000KTotal Submissions: 141868Accepted: 34673 Description 描述 Problems involving the computation of exact values of very large magnitude and precision are common. 高精度、大数值的计算问题是很常见的&…
datatable无法设置横向滚动条(设置无效)
datatable设置横向滚动条无效 js如下： 页面如下： 设置 scrollx 属性为true时，还需在 table 添加 style"white-space: nowrap; "最终效果： 转载于:https://www.cnblogs.com/renzp/p/10069594.html
水晶报表导出数据并实现打印
要在里一个页面上进行操作 ReportDocument rdocument new ReportDocument(); //公用打印方法 ExportCrystalL ExCrystal new ExportCrystalL(); User u new User(); #region 加载页面 protected void Page_Load(object sender, EventArgs e) { if (!IsPostB…
1130 Infix Expression
考察：DFS进行中序遍历。 注意：给除了根节点以外的父节点加左右括号。 AC代码 #include<cstdio> #include<iostream> #include<set> #include<vector> #include<map> #include<algorithm> #include<cmath> …
学习笔记之vue根据权限动态添加路由
路由守卫判断 router.beforeEach((to, from, next) > {if (to.path /login) {sessionStorage.removeItem(user);}if (!user && to.path ! /login&&location.search ! ?validate) {next({ path: /login })} else {next()} }) 复制代码 点击登陆后ÿ…
javascript重置（base层）（。。。。不完整）
1、nextSibling浏览器兼容问题 <ul><li id"item1"></li><li id"item2"></li><li id"item3"></li> </ul> var item1document.getElementById("item1"); alert(item1.nextSibling.id);…
java myeclipse jar 导出问题
1.工程 jdk要和实际jdk最好一个版本;2.有外部导入的jar,导出时应用manifest，设置外部引用JAR。例如：Manifest-Version: 1.0 Sealed: true Class-Path: lib/log4j-1.2.8.jar lib/xercesImpl.jar Main-Class: com.unimoco.mmsplatform.handler.MMSMOCenter…
漫谈回溯(未完待续)
将不使用优化算法、直接用朴素算法来解决问题的做法称为暴力法。 回溯是带优化的穷举。 回溯是具有界限函数的深度优先搜索。
sendStickyBroadcast和sendStickyOrderedBroadcast
sendStickyBroadcast和sendStickyOrderedBroadcast - 牛仔的移动开发博客 - 博客频道 - CSDN.NET sendStickyBroadcast和sendStickyOrderedBroadcast发出的广播会一直滞留（等待），以便有人注册这则广播消息后能尽快的收到这条广播。其他功能与…
固定资产打印条码标签应用方案
条码在固定资产管理中的应用方案： 应用客户案例： 河南省交通规划勘察设计院 黄河水文勘察测绘局 以实物管理为基础，以条码技术的应用为特点。通过先进的条码技术对固定资产实物从购置、领用、转移、盘点、清理到报废等方面进行全方位准确监管…
有关于诚信：唐骏学历门
提高造假的成本 - 南桥的博客 唐骏的学历门曝光后，我回想起过去的一件往事来。我读博士的时候，有人找我合作，在其介绍材料里写“博士”，我赶紧写信纠正，说自己是“博士生”（doctoral student)，而…
1115 Counting Nodes in a BST
我的DFS void DFS(Node* root){if(rootNULL)return;if(root->lchild){root->lchild->layer root->layer1;cnt[root->lchild->layer] ;maxLayer max(maxLayer,root->lchild->layer);DFS(root->lchild);}if(root->rchild){root->rchild->…
必会重构技巧：使用多态替换条件
使用多态替换条件：指在进行类型检查和执行某些类型操作时，最好将算法封装在类中，并且使用多态来对代码中的调用进行抽象 举例理解：看定义可能比较迷糊，其实说的简单一点，对于使用分支语句并且分支条件是和…
深度分析Java的枚举类型——枚举的线程安全性及序列化问题
点击关注，快速进阶高级架构师作者：Hollis写在前面：Java SE5提供了一种新的类型-Java的枚举类型，关键字enum可以将一组具名的值的有限集合创建为一种新的类型，而这些具名的值可以作为常规的程序组件使用，这是…