There is a stick of length L, and you will cut this stick N times.
Suppose the left end of the stick is initially placed at position 0 on the number line, and the right end is at position L on the number line. Each cut is specified by a number between 0 and L, representing the position where the cut will be made. You will cut the stick at this position into two pieces, and the cost of each cut equals the length of the stick being cut.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains two integers N and L. The next N lines contain two integers X and i, where X represents the position on the cut stick, and i indicates that this is the i-th cut among all cuts. It is guaranteed that i is an integer between [1, N] and does not repeat. | Output a single integer representing the total cutting cost. The answer may exceed 2^{31} but will not exceed 2^{60}. |
| 3 7 2 2 3 1 5 3 | 14 |
Thought Process
Use binary search to determine which segment the cut should be made in. Maintain an array to store the positions of each cut, including the initial start and end points. The cost of making a cut is the length of the segment where the cut is made.
Sample Code－ZeroJudge F607: Cutting Cost
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, L;
cin >> N >> L;
map<int, int>MAP;
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
MAP[b] = a;
}
vector<int> line;
line.push_back(0);
line.push_back(L);
long long int ans = 0;
for (auto it:MAP) {
const int knife = it.second;
int L = 0, R = line.size();
while (L <= R) {
const int middle = (L + R) / 2;
if (knife > line[middle]) L = middle + 1;
else R = middle - 1;
}
const long long int len = line[L] - line[R];
ans += len;
line.insert(line.begin()+L, knife);
}
cout << ans << "\n";
}
//ZeroJudge F607
//Dr. SeanXD