【工资计算 / 2】

题目

枚举

#include <bits/stdc++.h>
using namespace std;
int T;
int a[] = {0,1500,4500,9000,35000,55000,80000,1000000};
int b[] = {0,3,10,20,25,30,35,45};
int check(int x)
{if(x <= 3500) return x;x -= 3500;int tax = 0;for(int i = 1; i < 8; i++){if(x >= a[i-1]){tax += (min(x, a[i]) - a[i-1]) / 100 * b[i];}}return x + 3500 - tax;
}
int main()
{cin >> T;for(int x = 0; ; x += 100){if(check(x) == T){cout << x;break;}}return 0;
}

右区间二分

#include <bits/stdc++.h>
using namespace std;
int T;
int a[] = {0, 1500, 4500, 9000, 35000, 55000, 80000, 1000000};
int b[] = {0, 3, 10, 20, 25, 30, 35, 45};
int check(int x)
{if(x <= 3500) return x;x -= 3500;double tax = 0;for(int i = 1; i < 8; i++){if(x >= a[i-1]){tax += (double)(min(x, a[i]) - a[i-1]) / 100 * b[i];}}return x + 3500 - tax;
}
int main()
{cin >> T;int l = T, r = T * 2;while (l < r){int mid = (l + r) >> 1;if(check(mid) >= T) r = mid;else l = mid + 1;}cout << l;return 0;
}

左区间二分(错，注意答案必须是100的倍数，结合精度丢失，可以判断必须采用右区间二分)

比如check(10000) （右区间边界）= check(10001)（左区间边界） = 9255

check(9999) < 9255

如果右区间二分，会得到10000，左区间二分会得到 >= 10001的值

#include <bits/stdc++.h>
using namespace std;
int T;
int a[] = {0, 1500, 4500, 9000, 35000, 55000, 80000, 1000000};
int b[] = {0, 3, 10, 20, 25, 30, 35, 45};
int check(int x)
{if(x <= 3500) return x;x -= 3500;double tax = 0;for(int i = 1; i < 8; i++){if(x >= a[i-1]){tax += (double)(min(x, a[i]) - a[i-1]) / 100 * b[i];}}return x + 3500 - tax;
}
int main()
{cin >> T;int l = T, r = T * 2;while (l < r){int mid = (l + r + 1) >> 1;if(check(mid) <= T) l = mid;else r = mid-1;}cout << l;return 0;
}