团体程序设计天梯赛-练习集 - L2-018 多项式A除以B（25 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=1e4+10;
structnode{
inte;
doubled;
}nds[maxn], tnds[maxn], rnds[maxn];
set<int,greater<int>>st;
intmain()
{
intn,m,e,te;
doubled,td;
scanf("%d",&n);
for(inti=0;i<n;i++)
    {
scanf("%d%lf",&e,&d);
st.insert(e);
tnds[e].e=e;
tnds[e].d=d;
    }
scanf("%d",&m);
for(inti=0;i<m;i++) scanf("%d%lf",&nds[i].e,&nds[i].d);
intl=0, k=0;
while(1)
    {
autoit=st.begin();
e=*it;
if(e<nds[0].e) break; // 如果被除项最高次小于除项的最高次 breakte=tnds[e].e, td=tnds[e].d;
rnds[l].e=(te-=nds[0].e); // 记录商rnds[l++].d=(td/=nds[0].d);
for(inti=0;i<m;i++) // 更新被除项（最终为余项）        {
e=nds[i].e+te;
d=nds[i].d*td;
tnds[e].d-=d;
tnds[e].e=e;
st.insert(e);
        }
st.erase(st.begin()); // 每次消除最大    }
for(inti=0;i<l;i++) if(fabs(rnds[i].d)>4*1e-2) k++;
if(k==0) puts("0 0 0.0");
else    {
printf("%d",k);
for(inti=0;i<l;i++)
if(fabs(rnds[i].d)>4*1e-2) printf(" %d %.1f",rnds[i].e,rnds[i].d);
puts("");
    }
l=0;
for(inti=nds[0].e-1;i>=0;i--) if(fabs(tnds[i].d)>4*1e-2) l++;
if(l==0){puts("0 0 0.0"); return0;}
printf("%d",l);
for(inti=nds[0].e-1;i>=0;i--)
if(fabs(tnds[i].d)>4*1e-2) printf(" %d %.1f",tnds[i].e,tnds[i].d);
puts("");
return0;
}