(最近重刷PTA天梯赛的题目碰到这个题,还是无从下手,所以写篇博客记录一下)
//输入是以指数递减的形式依次输入每一项4 4 1 2 -3 1 -1 0 -13 2 3 1 -2 0 1//输出和输入格式一样,依次输出商和余数3 2 0.3 1 0.2 0 -1.01 1 -3.1 样例图解 题目代码 #include <bits/stdc++.h>using namespace std;typedef long long ll;#define lowbit(x) ((x) & (-x))const int inf = 0x3f3f3f3f;const int N = 1010;double c1[N], c2[N], ans[N]; //ans数组保存商,c1数组最终的值就是余数int max1, max2;void input(double *arr, int cnt, int &m) { int e; double val; while (cnt--) { cin >> e >> val; arr[e] = val; m = max(m, e); }}void output(double *arr, int e) { int cnt = 0; for (int i = 0; i <= e; i++) if (abs(arr[i]) >= 0.05) //四舍五入后为0.0的项不会输出 cnt++; if (cnt == 0) cout << "0 0 0.0"; else { cout << cnt; for (int i = e; i >= 0; i--) { if (abs(arr[i]) >= 0.05) printf(" %d %.1f", i, arr[i]); } }}int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int n; cin >> n, input(c1, n, max1); cin >> n, input(c2, n, max2); int d = max1 - max2;//保存商的最高项 while (max1 >= max2) { double k = c1[max1] / c2[max2]; ans[max1 - max2] = k; for (int i = max1, j = max2; i >= 0 && j >= 0; i--, j--) c1[i] -= c2[j] * k; max1--; } output(ans, d); cout << endl; output(c1, max1); return 0;}