pat1044专题

PAT1044. Shopping in Mars (25)(二分)

题意: 给出一系列数字,要求输出子序列使其和等于m,如果没有等于m的子序列就输出和减去m的差最小的子序列 要点: 这题的时间要求是100ms,n的量级是10^5,O(n^2)是肯定不行了,但我一开始算了一下O(nlogn)觉得不大行,就一直在想O(n)的方法,实际上O(nlogn)=10^5*17=1.7*10^6差不多是行的。接下来二分就行了。 #include<iostream>#i