洛谷P4343 自动刷题机

url: https://www.luogu.com.cn/problem/P4343

tag:
二分,模拟

思路:
思路比较简单,根据题目可以知道当n越小时切出来的题目数量越多,根据这个来二分。分别二分出一个最小值和一个最大值。这道题是细节比较 恶心(bushi 多,需要注意的点比较多。第一个是二分的范围,题目只有一个xi的范围是1e-9到1e9,经测试,r开到1e9范围比较小,看了题解之后发现需要开到1e18.然后这里就有一个问题,因为超过了1e9所以变量不能放到main()函数中,只能放到外面当全局变量。然后如果是mid要用long long类型,记得check函数的函数签名中变量的类型也要是long long。第二个细节是l要从1开始,不能从0开始。第三个细节是,题目没有保证说如果其中一个答案比如最小值存在,另外一个答案就会存在,所以对于最小值和最大值都要进行验证。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5. const int N = 1e5 + 10;
  6. long long n, k, l ,r;
  7. long long p[N];
  8. long long check (long long x)
  9. {
  10. long long sum = 0, cnt = 0;
  11. for (int i = 0; i < n; i ++)
  12. {
  13. if (p[i] > 0) sum += p[i];
  14. else sum = max((long long)0, sum + p[i]);
  15. if (sum >= x)
  16. {
  17. sum = 0;
  18. cnt ++;
  19. }
  20. }
  21. return cnt;
  22. }
  23. int main()
  24. {
  25. scanf("%lld%lld", &n, &k);
  26. for (int i = 0; i < n; i ++) scanf("%lld", &p[i]);
  27. l = 1, r = 1e18;
  28. while (l < r)
  29. {
  30. long long mid = (l + r) >> 1;
  31. if (check(mid) <= k) r = mid;
  32. else l = mid + 1;
  33. }
  34. long long tmp;
  35. if (check(l) != k)
  36. {
  37. cout << -1 ;
  38. return 0;
  39. }
  40. else tmp = l;
  41. l = 1, r = 1e18;
  42. while (l < r)
  43. {
  44. long long mid = (l + r + 1) >> 1;
  45. if (check(mid) >= k) l = mid;
  46. else r = mid - 1;
  47. }
  48. if (check(l) != k)
  49. {
  50. cout << -1 ;
  51. return 0;
  52. }
  53. else cout << tmp << ' ' << l;
  54. return 0;
  55. }
添加新评论