AKSZ-月赛题2
2024-05-01 20:05:37
发布于:广东
这道题是一个典型的贪心算法题目,需要找到一个合适的方案,使得税收标准最大化。以下是这道题的解题思路:
- 定义一个结构体
City
来表示每个城市的年收入、人口数量和税收标准。 - 使用
sort
函数将城市按照税收标准从高到低排序。 - 定义一个函数
checkMid
来检查在给定的税收标准下是否能选取符合条件的城市。 - 使用二分查找法在可能的税收标准范围内寻找最大的税收标准。
- 输出最大的税收标准。
以上是代码的逻辑,下面解释一下各个部分的作用:
City
结构体:用来表示城市的年收入、人口数量和税收标准。构造函数会计算税收标准。compareTaxStandard
函数:用来排序城市,按照税收标准从高到低排序。checkMid
函数:在给定的税收标准下,检查是否能够选取符合条件的城市。这个函数会计算每个城市的差值(收入 - 税收标准 * 人口),排序后取前 k 个城市的差值求和,如果大于等于 0,则说明符合条件。findMaxTaxStandard
函数:使用二分查找法在可能的税收标准范围内寻找最大的税收标准。不断调用checkMid
函数来进行判断。main
函数:读取输入数据,调用相应的函数,并输出结果。
下面是代码实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct City {
long long income, population;
double taxStandard;
City(long long inc, long long pop) : income(inc), population(pop) {
taxStandard = (double)income / population;
}
};
bool compareTaxStandard(const City& city1, const City& city2) {
return city1.taxStandard > city2.taxStandard;
}
bool checkMid(vector<City>& cities, int k, double mid) {
vector<double> diffs;
for (auto& city : cities) {
diffs.push_back(city.income - mid * city.population);
}
sort(diffs.begin(), diffs.end(), greater<double>());
double sum = 0;
for (int i = 0; i < k; i++) {
sum += diffs[i];
}
return sum >= 0;
}
double findMaxTaxStandard(vector<City>& cities, int k) {
double left = 0, right = 1e9;
double ans = 0;
while (right - left > 1e-6) {
double mid = (left + right) / 2;
if (checkMid(cities, k, mid)) {
ans = mid;
left = mid;
} else {
right = mid;
}
}
return ans;
}
int main() {
freopen("moretaxes.in", "r", stdin);
freopen("moretaxes.out", "w", stdout);
int n, k;
cin >> n >> k;
vector<City> cities;
for (int i = 0; i < n; i++) {
long long inc, pop;
cin >> inc >> pop;
cities.push_back(City(inc, pop));
}
sort(cities.begin(), cities.end(), compareTaxStandard);
double maxTaxStandard = findMaxTaxStandard(cities, k);
cout << fixed << setprecision(6) << maxTaxStandard << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
这里空空如也
有帮助,赞一个