This puzzle from Timus Online Judge is interesting and kinda practical in reality. This problem can be used to study the traffic jams.
Put it simpler in other words. Given a water pipe, the maximum throughput (for any time) is k (e.g. cans). There are n moments where numbers of cans flow into the pipe. Compute the number of cans standing in the water pipe.
The quickest solution is to simulate the scenario. We use a variable to represent the remain throughput, we update it accordingly each time when a new traffic arrives. If too much traffic (larger than the current maximum), update it to zero.
The following C++ solution is 
which reads each moment traffic and updates at the same time.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include <iostream> using namespace std; int main() { int k, n; cin >> k >> n; int t; int s = 0; // the remainder for (int i = 0; i < n; i ++) { cin >> t; if (t + s > k) { s = (t + s - k); } else { s = 0; } } cout << s << endl; return (0); } |
#include <iostream>
using namespace std;
int main()
{
int k, n;
cin >> k >> n;
int t;
int s = 0; // the remainder
for (int i = 0; i < n; i ++)
{
cin >> t;
if (t + s > k)
{
s = (t + s - k);
}
else
{
s = 0;
}
}
cout << s << endl;
return (0);
}–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
323 wordsloading...
Last Post: Coding Exercise - C++ - Codeforces - B. The least round way - Dynamic Programming
Next Post: Reverse List/Tuple/String in Python
