立志用最少的代碼做最高效的表達(dá)

---

PAT甲級(jí)最優(yōu)題解——>傳送門(mén)

---

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 (≤10?5??), the total number of diamonds on the chain, and M (≤10?8??), the amount that the customer has to pay. Then the next line contains N positive numbers D?1???D?N?? (D?i??≤10?3?? 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

---

題意：給定數(shù)N，K，N個(gè)數(shù)。在N個(gè)數(shù)中求出若干個(gè)連續(xù)子序列，其和為K，順序輸出。 如果沒(méi)有和為K的子序列， 則輸出其和大于K的最小連續(xù)子序列。

算法設(shè)計(jì)：采用滑動(dòng)窗口設(shè)計(jì)，定義left與right兩個(gè)變量，第一遍循環(huán)尋找和為K的最小子序列，輸出。 如果沒(méi)找到，就記錄期間出現(xiàn)的大于K的最小和的值。 進(jìn)行第二遍循環(huán)，輸出。

注意：如果沒(méi)有和為K的子序列， 并不是輸出所有大于K的子序列， 而是其值最小的子序列。 如果有一個(gè)就輸出一個(gè)， 如果等于這個(gè)值的子序列數(shù)量不為1，則輸出多個(gè)。

具體算法邏輯請(qǐng)參考代碼

---

#include<bits/stdc++.h> using namespace std;void solve(int* ary, int len, int cost, int& max_val) {int i = 0, j = 0, sum = 0;while(i <= j) {while(j < len && sum < cost) sum += ary[j++];//如果沒(méi)有正好相等的數(shù)據(jù)對(duì)，這一步要求出大于且最小的數(shù)據(jù)對(duì)。 供下一步用 if(max_val > sum && sum >= cost) max_val = sum; if(sum == cost) cout << i+1 << '-' << j << '\n';sum -= ary[i++];} }int main() {int ary[100010] = {0};int num, cost, max_val = 0;cin >> num >> cost;for(int i = 0; i < num; i++) {cin >> ary[i];max_val += ary[i];}solve(ary, num, cost, max_val);if(max_val > cost) solve(ary, num, max_val, max_val);return 0; }

---

耗時(shí)：

---

求贊哦~ |?･ω･` )

總結(jié)

以上是生活随笔為你收集整理的【题意分析】1044 Shopping in Mars (25 分)【滑动窗口】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。