PAT 1044 Shopping in Mars[二分][难]
1044 Shopping in Mars(25 分)
Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:
- Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15).
- Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).
- Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15).
Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.
If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤105), the total number of diamonds on the chain, and M (≤108), the amount that the customer has to pay. Then the next line contains N positive numbers D1⋯DN (Di≤103 for all i=1,⋯,N) which are the values of the diamonds. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print i-j
in a line for each pair of i
≤ j
such that Di
+ ... + Dj
= M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i
.
If there is no solution, output i-j
for pairs of i
≤ j
such that Di
+ ... + Dj
>M with (Di
+ ... + Dj
−M) minimized. Again all the solutions must be printed in increasing order of i
.
It is guaranteed that the total value of diamonds is sufficient to pay the given amount.
Sample Input 1:
16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13
Sample Output 1:
1-5
4-6
7-8
11-11
Sample Input 2:
5 13
2 4 5 7 9
Sample Output 2:
2-4
4-5
题目大意:给出一串数表示钻石的价值,并且给出m,如果有一连串钻石价值正好等于m,那么就输出这一串;如果没有正好相等的和,那么就输出那些>m,并且和m差值最小的!
//第一次提交这样,就是通过两层循环来做,
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include <vector> #include <cmath> using namespace std; int dio[100001]; int main() { int n,m; cin>>n>>m; for(int i=0;i<n;i++){ cin>>dio[i]; } bool flag=false; for(int i=0;i<n;i++){ int sum=0; for(int j=i;j<n;j++){ sum+=dio[j]; if(sum==m){ flag=true; cout<<i+1<<'-'<<j+1<<'\n';break; } } } vector<int> vt; if(!flag){//如果没有解。 int mini=100001; for(int i=0;i<n;i++){ int sum=0; for(int j=i;j<n;j++){ sum+=dio[j]; if(sum>m&&sum-m<mini){ vt.clear(); vt.push_back(i+1); vt.push_back(j+1); //cout<<i+1<<"="<<j+1<<" "<<sum<<'\n'; mini=sum-m;break; }else if(sum>m&&sum-m==mini){ vt.push_back(i+1); vt.push_back(j+1); // cout<<i+1<<"+"<<j+1<<'\n'; break; } } } } for(int i=0;i<vt.size();i+=2){ cout<<vt[i]<<'-'<<vt[i+1]<<'\n'; } return 0; }
//但是提交到牛客网上,
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为40.00%
//顿时感觉凉凉。提交到pat上,2,3,5测试点运行超时。
代码来自:https://www.liuchuo.net/archives/2939
#include <iostream> #include <vector> using namespace std; vector<int> sum, resultArr; int n, m; void Func(int i, int &j, int &tempsum) {//这个求的是从i到j的和。 //表面上是left,但是while里的if条件仍然只是>=m int left = i, right = n; while(left < right) { int mid = (left + right) / 2; if(sum[mid] - sum[i-1] >= m) right = mid;//必须是=mid,如果是mid-1,那很有可能和就不够了。 else left = mid + 1; } j = right;//传引用的话,是不用return的, tempsum = sum[j] - sum[i-1]; } int main() { scanf("%d%d", &n, &m); sum.resize(n+1); for(int i = 1; i <= n; i++) { scanf("%d", &sum[i]); sum[i] += sum[i-1];//这是前缀和? } int minans = sum[n]; for(int i = 1; i <= n; i++) { int j, tempsum; Func(i, j, tempsum);//直接传引用。 if(tempsum > minans) continue;//感觉这一句不用吧,肯定不会大于的。 //明白了,这个在i=1第一次循环的时候是没用,但是minans更新之后就有用了。 //判断>当前的都不选择。 if(tempsum >= m) { if(tempsum < minans) { resultArr.clear(); minans = tempsum; } resultArr.push_back(i); resultArr.push_back(j); } } for(int i = 0; i < resultArr.size(); i += 2) printf("%d-%d\n", resultArr[i], resultArr[i+1]); return 0; }
//学习了,不用直接去找是否有=m,或者没有等于的,都一样的方式去遍历查找。
1.当程序正常超时时,需要考虑二分法。
2.使用引用传值,减少函数调用时间。
3.这里的mid求的不是到left的和,而是到i的和!和往常的不一样。
//这个二分我感觉确实挺难的,相不到,
代码来自:https://www.cnblogs.com/chenxiwenruo/p/6677802.html
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <vector> #define INF 0x3f3f3f3f using namespace std; const int maxn=100000+5; int n,m; int diamond[maxn]; struct Ans{ int i,j; }; vector<Ans> ans; int main() { scanf("%d %d\n",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&diamond[i]); int minlost=INF; Ans tmp; int sum=0; int start=1; for(int i=1;i<=n;i++){ sum+=diamond[i]; //printf("%d %d %d %d %d\n",start,i,sum,sum-m,minlost); if(sum<m) continue; if(sum-m<=minlost){ if(sum-m<minlost){ ans.clear(); minlost=sum-m; } tmp.i=start; tmp.j=i; ans.push_back(tmp); } if(sum>=m && start<i){//这里是在做什么? sum-=diamond[i];//明白了,-钻石i的值,和钻石start的值, i--;//如果减去diamond[i],并且减去start的值,那么总和肯定小于m,那么 sum-=diamond[start];//肯定要就着i往下加了。 start++;//目前的sum肯定达不到m,所以肯定需要往后加。 printf("%d\n",sum); } } for(int i=0;i<ans.size();i++){ printf("%d-%d\n",ans[i].i,ans[i].j); } return 0; }
//这个也写得很好,但是我有点不太理解。
// 但是接着说上述二分方法的话,也就是原来二分,求和之后二分的方法。
相关文章
- ORA-01088: shutdown in progress – operation not permitted until restart ORACLE 报错 故障修复 远程处理
- ORA-22140: given size [string] must be in the range of 0 to [string] ORACLE 报错 故障修复 远程处理
- ORA-25505: the system is not in quiesced state ORACLE 报错 故障修复 远程处理
- ORA-26652: Capture string did not start properly and is currently in state string ORACLE 报错 故障修复 远程处理
- ORA-29982: Table type not supported for query registration in guaranteed mode ORACLE 报错 故障修复 远程处理
- ORA-30176: invalid format code used in the format string ORACLE 报错 故障修复 远程处理
- ORA-32041: UNION ALL operation in recursive WITH clause must have only two branches ORACLE 报错 故障修复 远程处理
- ORA-39819: The OCI_ATTR_DIRPATH_NO_INDEX_ERRORS attribute cannot be set to TRUE in direct path parallel loads. ORACLE 报错 故障修复 远程处理
- ORA-41696: invalid operator in the having clause: string ORACLE 报错 故障修复 远程处理
- ORA-53100: The repository data model is in invalid state. ORACLE 报错 故障修复 远程处理
- ORA-01078: failure in processing system parameters ORACLE 报错 故障修复 远程处理
- ORA-01234: cannot end backup of file string – file is in use or recovery ORACLE 报错 故障修复 远程处理
- ORA-14646: Specified alter table operation involving compression cannot be performed in the presence of usable bitmap indexes ORACLE 报错 故障修复 远程处理
- ORA-16236: Logical Standby metadata operation in progress ORACLE 报错 故障修复 远程处理
- Oracle替代in:抛弃IN,开启新的查询方式(oracle代替in)
- Sending email in SAP ABAP using Cl_BCS class详解编程语言
- MySQL查询优化:从IN中获取更高性能(mysql查询优化in)
- MySQL使用IN运算符的查询实践(mysql使用in查询)
- 子查询MySQL联表IN子查询:实现跨表快速查询(mysql联表in)
- 用法Oracle IN 用法简介(oracle的in)
- MySQL中IN的用法和意义(mysql中in的意思)
- MySQL中IN函数的使用及作用解析(mysql中in作用)
- 探索ORACLE中IN关键字的使用(in怎么使用oracle)
- MySQL实现不在某个范围内的查询当字段不在给定值列表中时,使用NOT IN语法(mysql 不in)
- 深入理解Oracle中IN运算符的用法(oracle中的in用法)
- 利用Oracle中的IN子句改善查询效率(oracle中的in子句)
- 提升Oracle IN操作中的性能改进(oracle in的性能)
- Oracle In 优势与劣势分析(oracle in优缺点)