文章目录

  • 一.田地丈量
    • 1.题目内容
    • 2.题意简述
    • 3.题意分析
    • 4.完整代码
  • 二.垦田计划
    • 1.题目内容
    • 2.题意简述
    • 3.题意分析
    • 4.完整代码

一.田地丈量

1.题目内容


2.题意简述

在坐标轴上给定n个矩形,并计算n个矩形（不考虑重合）与小岛相交面积(绿色区域)的和。

3.题意分析

我们采用枚举的方法进行计算，也就是分成9部分也就是9种情况，时间复杂度O(N),不需要考察算法，只需要注意边界问题！
图解：

4.完整代码

方法1:

#includeusing namespace std;int main() {int n, a, b;int x1, y1, x2, y2;long long int sum = 0;scanf("%d%d%d", &n, &a, &b);for (int i = 1; i <= n; i++) {scanf("%d%d%d%d", &x1, &y1, &x2, &y2);if(x1>=0&&y1>=0&&x2<=a&&y2<=b)sum+=(y2-y1)*(x2-x1);else if(x1<0&&x2>0&&y1<0&&y2>0)sum+=y2*x2;else if(x1>=0&&x2<=a&&y1<0&&y2>0)sum+=y2*(x2-x1);else if(x1<a&&x2>a&&y1<0&&y2>0)sum+=(a-x1)*y2;else if(x1<a&&x2>a&&y1>=0&&y2<=b)sum+=(y2-y1)*(a-x1);else if(x1<a&&x2>a&&y1<b&&y2>b)sum+=(b-y1)*(a-x1);else if(x1>=0&&x2<=a&&y1<b&&y2>b)sum+=(b-y1)*(x2-x1); else if(x1<0&&x2>0&&y1<b&&y2>b) sum+=x2*(b-y1);else if(x1<0&&x2>0&&y1>=0&&y2<=b)sum+=x2*(y2-y1);}printf("%lld",sum);return 0;}

方法2:

#include#includeusing namespace std;int x1, y1, x2, y2;int main() {int n, a, b, x, y;long long sum = 0;scanf("%d%d%d", &n, &a, &b);for (int i = 1; i <= n; i++) {scanf("%d%d%d%d", &x1, &y1, &x2, &y2);x = min(a, x2) - max(0, x1);y = min(b, y2) - max(0, y1);if (x >= 0 && y >= 0)sum += x * y;}printf("%lld", sum);return 0;}

补充:这里方法2使用max，min函数计算每个矩形和小岛相交面积的和，充分考虑边界问题，应该是最简便的方法。

提交结果：

二.垦田计划

1.题目内容



2.题意简述

我们由若干田地，这些田地我们垦种，可以同时耕种，可以使用资源减少耕种时间，但耕种时间不少于k天。需要考虑如何分配资源使耕种天数最少？

3.题意分析

这里我们我们需要利用一个容器来存储对应的耕作消耗情况,这里我们利用容器cc[t[i]]=c[i],来进行存储，我们从高到低进行判断，因为考察的重心在最大值！

4.完整代码

#include#includeusing namespace std;const int N = 100100;typedef long long ll;ll t[N], c[N];ll cc[N];int main() {ll n, m, k, maxn = 0;cin >> n >> m >> k;for (int i = 0; i < n; i++) {cin >> t[i] >> c[i];cc[t[i]] += c[i];maxn = max(maxn, t[i]);}for (int i = maxn; i >= k; i--) {if (m > cc[i]) {if (i == k) {cout << k << endl;break;}m = m - cc[i];cc[i - 1] = cc[i - 1] + cc[i];}else{cout << i << endl;break;}}}

提交结果: