纯数学。对于每一个unit,同时计算来回所要的时间。
有N个路段(N<=100000),每个路段要么是上坡路要么是平路要么是下坡路。记走完一段上坡路、平路、下坡路所需的时间分别为U,F,D。现在告诉你N段路的路况。规定要在限定的时间内回到起点,问最多能走完几个路段?
这里可以一边读入一边计算:每次读入一个路段,如果这个路段是上坡路或者下坡路,就把剩余时间减去U+D,否则减去2*F。如果当前时间不足就输出前一段路的编号并退出。时间复杂度是O(N)。
/* * POJ_3672.cpp * * Created on: 2013年11月26日 * Author: Administrator */ #include <iostream> #include <cstdio> using namespace std; int main() { int m, t, u, f, d; scanf("%d%d%d%d%d", &m, &t, &u, &f, &d);//***这里不要写成while(scanf()!=EOF)的形式,否则会TLE char ch; int ans = 0; bool flag = false; while (t--) { if (flag) { continue; } scanf(" %c", &ch); if (ch == 'u' || ch == 'd') { m -= u; m -= d; } else if (ch == 'f') { m -= 2 * f; } if (m >= 0) { ans++; } else { flag = true; } } printf("%d\n", ans); // cout<<ans<<endl; return 0; }