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

tag:
前缀和

思路:
先求前缀和,然后遍历右下端点,求出每个对应的子矩阵的总和,判断是否大于res,如果大的话就更新res和坐标x,y。最后输出x和y即可。

ps:这道题很简单,本来不应该传博客的,但是觉得自己写的好优美,忍不住传一下,以后偶尔可以翻出来看看。真的好优美感觉。

代码:

  1. #include <iostream>
  2. using namespace std;
  3. const int N = 1010;
  4. long long p[N][N];
  5. int n, m , c;
  6. int main()
  7. {
  8. cin >> n >> m >> c;
  9. for (int i = 1; i <= n; i ++)
  10. for (int j = 1; j <= n; j ++)
  11. {
  12. cin >> p[i][j];
  13. p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
  14. }
  15. long long res = 0, x, y;
  16. for (int i = c; i <= n; i ++)
  17. for (int j = c; j <= m; j ++)
  18. {
  19. long long tmp = p[i][j] - p[i - c][j] - p[i][j - c] + p[i - c][j - c];
  20. if (tmp > res)
  21. {
  22. res = tmp;
  23. x = i - c + 1;
  24. y = j - c + 1;
  25. }
  26. }
  27. cout << x << ' ' << y;
  28. return 0;
  29. }

问题描述

小U计划进行一场从地点A到地点B的徒步旅行,旅行总共需要 M 天。为了在旅途中确保安全,小U每天都需要消耗一份食物。在路程中,小U会经过一些补给站,这些补给站分布在不同的天数上,且每个补给站的食物价格各不相同。

小U需要在这些补给站中购买食物,以确保每天都有足够的食物。现在她想知道,如何规划在不同补给站的购买策略,以使她能够花费最少的钱顺利完成这次旅行。

  • M:总路程所需的天数。
  • N:路上补给站的数量。
  • p:每个补给站的描述,包含两个数字 A 和 B,表示第 A 天有一个补给站,并且该站每份食物的价格为 B 元。

保证第0天一定有一个补给站,并且补给站是按顺序出现的。


测试样例

样例1:

输入:m = 5 ,n = 4 ,p = [[0, 2], [1, 3], [2, 1], [3, 2]]
输出:7

样例2:

输入:m = 6 ,n = 5 ,p = [[0, 1], [1, 5], [2, 2], [3, 4], [5, 1]]
输出:6

样例3:

输入:m = 4 ,n = 3 ,p = [[0, 3], [2, 2], [3, 1]]
输出:9

代码:

  1. int solution(int m, int n, std::vector<std::vector<int>> p) {
  2. // 在末尾添加一个虚拟站点表示终点,价格设为0(方便处理,但不会实际购买)
  3. p.push_back({m, 0});
  4. int totalCost = 0;
  5. int currentIndex = 0; // 当前站点索引
  6. while (currentIndex < p.size() - 1) { // 最后一个虚拟站点不作为实际购买点
  7. int currentDay = p[currentIndex][0];
  8. int currentPrice = p[currentIndex][1];
  9. int nextIndex = currentIndex + 1;
  10. // 找到下一个比当前站价格低的站点或者终点
  11. while (nextIndex < p.size() && p[nextIndex][1] >= currentPrice) {
  12. nextIndex++;
  13. }
  14. // 如果未找到更便宜的,nextIndex 会指向虚拟终点站
  15. if (nextIndex == p.size()) {
  16. nextIndex = p.size() - 1;
  17. }
  18. int nextDay = p[nextIndex][0];
  19. // 计算从当前站到目标站之间需要的天数差
  20. int daysNeeded = nextDay - currentDay;
  21. // 在当前站购买足够的食物以覆盖到下一个更便宜的站或终点
  22. totalCost += daysNeeded * currentPrice;
  23. // 将当前站点移动到找到的更便宜的站点
  24. currentIndex = nextIndex;
  25. }
  26. return totalCost;
  27. }

tag:
贪心

思路:
用贪心的策略,每次都找一个花费比当前补给站少的点,然后买刚好到那个补给站的食物。然后将当前的位置更新到那个补给站,直到到达终点。

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. }

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

tag:
最大子数列,Kadane 算法,动态规划

思路:
使用动态规划得方法来求解,用两个变量currentSum,和maxSum,分别来维护以当前位置结尾的最大子段和以及全局的最大子段和。状态转移分别是currentSum = max(a, currentSum + a), maxSum = max(maxSum, currentSum).最后输出maxSum即可。细节:一开始可以先定义为最小值-0x3f3f3f3f这样可以避免漏掉负数,以及因为要求和所以最好开long long避免爆int。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5. int n;
  6. int main()
  7. {
  8. scanf("%d", &n);
  9. long long currentSum = -0x3f3f3f3f, maxSum = -0x3f3f3f3f;
  10. for (int i = 0; i < n; i ++)
  11. {
  12. long long a;
  13. scanf("%lld", &a);
  14. currentSum = max(a, currentSum + a);
  15. maxSum = max(maxSum, currentSum);
  16. }
  17. cout << maxSum << endl;
  18. return 0;
  19. }

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

tag:
哈夫曼(Huffman)树 , 优先队列

思路:因为每次合并果子需要的体力值是两堆果子的重量之和,所以为了让总的体力值最小,可以使用贪心的策略,每次都只合并所有堆中重量最小的两堆。因此可以使用优先队列,每次取出两个头节点,res += 两个节点值的和,再将和的值插入到优先队列,重复这个过程直到队列中只有一个值,最后输出res即可。

代码:

  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5. int main()
  6. {
  7. priority_queue<int, vector<int>, greater<int> > heap;
  8. int n;
  9. cin >> n;
  10. for (int i = 0; i < n; i ++)
  11. {
  12. int a;
  13. cin >> a;
  14. heap.push(a);
  15. }
  16. long long res = 0;
  17. while(heap.size() > 1)
  18. {
  19. int a = heap.top();
  20. heap.pop();
  21. int b = heap.top();
  22. heap.pop();
  23. res += a + b;
  24. heap.push(a + b);
  25. }
  26. cout << res << endl;
  27. return 0;
  28. }