A1044

A1044

//一次通了,但是运行超时,每次都做累加会非常耗时,原代码如下
#pragma warning(disable: 4996)
#include
#include
#include
#include

using namespace std;

long long binarySearch(long long* array, vector<long long*> &answer, long long left, long long right, long long value) {
long long mid, *diamonds = new long long[2];
diamonds[0] = left;
while (left < right) {
mid = (left + right) / 2;
if (accumulate(array + diamonds[0], array + mid + 1, 0) >= value) right = mid;
else left = mid + 1;
}
long long diff = accumulate(array + diamonds[0], array + left + 1, 0) - value;
diamonds[0]++;
diamonds[1] = left + 1;
answer.push_back(diamonds);
return diff;
}

int main(int argc, char argv[]) {
long long N, M;
scanf(“%lld %lld”, &N, &M);
long long *diamonds = new long long[N];
for (long long i = 0; i < N; i++)
scanf(“%lld”, &diamonds[i]);
vector<long long
> answer;
long long *diff = new long long[N];
long long minDiff = M;//最小的差值不会大过所需金额
for (long long i = 0; i < N; i++) {
diff[i] = binarySearch(diamonds, answer, i, N - 1, M);//如果没有刚好相等的就存到第一个大于所需金额的位置,记录每个序列和金额的差值,都没有则空
if (diff[i] >= 0 && minDiff > diff[i]) minDiff = diff[i];
}
for (long long i = 0; i < N; i++)
if (minDiff == diff[i])
printf(“%lld-%lld\n”, answer[i][0], answer[i][1]);
system(“pause”);
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×