3 条题解
-
5
感谢同学用户 - 2315 - 南阳理工学院OJ (fuquan.moe)
using namespace std; const int N = 1e5 + 10; long long arr[N], brr[N],l[N],r[N],x[N],n,m; int axx(int c)//差分 { brr[1] = m; for (int i = 2; i <= n; i++) brr[i] = 0; for (int i = 1; i <= c; i++) { brr[l[i]] -= x[i]; brr[r[i] + 1] += x[i]; } for (int i = 1; i <= n; i++) { arr[i] = arr[i - 1] + brr[i]; if (arr[i] <= 0)return 1; } return 0; } int main() { cin >> n >> m; brr[1] = m; for (int i = 1; i <= n; i++) cin >> l[i] >> r[i] >> x[i]; int i = 1, j = n; while (i < j)//二分时间,总共n秒 { int mad = (i + j) / 2; if (axx(mad))j = mad; else i = mad + 1; } if (j == n)//特判j=n的情况 { if (axx(n))cout << n;//如果炸断了就输出n else cout << "impossible";//如果n秒后炸不断,就输出impossible } else cout << j; }
信息
- ID
- 965
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 708
- 已通过
- 66
- 上传者