#43139: 解題思路
henry.rem.rem@gmail.com
(*ฅ́˘ฅ̀*)
學校
:
臺北市立松山高級中學
編號 : 278368
來源 : [1.161.32.250]
最後登入時間 ：
2024-11-23 23:58:32
因為需要往左一直走，並把路上的點數加起來
可以很容易聯想到前綴和
因此宣告一個vector存前綴和，再另外宣告一個int紀錄當前位置
執行任務時，需要先看看會不會走超過最後一個位置（繞一圈
如果超過，就會回到陣列起點，並把目標點數減掉走到底途中已經獲得的點數
if (currPosition != 0 && target > prefix[n - 1] - prefix[currPosition - 1]) {
target -= prefix[n - 1] - prefix[currPosition - 1]; //減掉已經獲得的點數
currPosition = 0; //回起點
}
然後繼續重複，直到需要的點數已經能夠在一圈內撿完
while (target > prefix[n - 1]) target -= prefix[n - 1]; //因為經過上述步驟，已經回到起點，故直接減掉prefix最後一項即可
剩下就二分搜找到停止點
while (l + 1 < r) {
mid = (l + r) / 2;
if (currPosition == 0) {
if (prefix[mid] >= target) r = mid;
else l = mid;
} else {
if (prefix[mid] - prefix[currPosition - 1] >= target) r = mid;
else l = mid;
}
}
currPosition = r + 1; //記得把停留位置往前移一格
#43292: Re: 解題思路
henry.rem.rem@gmail.com
(*ฅ́˘ฅ̀*)
學校
:
臺北市立松山高級中學
編號 : 278368
來源 : [1.161.32.250]
最後登入時間 ：
2024-11-23 23:58:32
因為需要往左一直走，並把路上的點數加起來
可以很容易聯想到前綴和
因此宣告一個vector存前綴和，再另外宣告一個int紀錄當前位置
執行任務時，需要先看看會不會走超過最後一個位置（繞一圈
如果超過，就會回到陣列起點，並把目標點數減掉走到底途中已經獲得的點數
if (currPosition != 0 && target > prefix[n - 1] - prefix[currPosition - 1]) {target -= prefix[n - 1] - prefix[currPosition - 1]; //減掉已經獲得的點數currPosition = 0; //回起點}然後繼續重複，直到需要的點數已經能夠在一圈內撿完
while (target > prefix[n - 1]) target -= prefix[n - 1]; //因為經過上述步驟，已經回到起點，故直接減掉prefix最後一項即可剩下就二分搜找到停止點while (l + 1 < r) {mid = (l + r) / 2;if (currPosition == 0) {if (prefix[mid] >= target) r = mid;else l = mid;} else {if (prefix[mid] - prefix[currPosition - 1] >= target) r = mid;else l = mid;}}currPosition = r + 1; //記得把停留位置往前移一格
啊啊複製錯了
最後應該是currPosition = (r + 1) % n;
才對
ZeroJudge Forum