2019多校第五场 HDU6627 equation（分数，解绝对值方程）

链接：HDU6627 equation

题意：

解方程：$\sum _{i=1}^N\left|a_i?x+b_i\right|=C$

其中

• $1\le N\le 10^5$

• $1\le a_i\le 1000$

• $?1000\le b_i\le 1000$

• $1\le C\le 10^9$

若有无穷多个解，输出"$?1$"；否则输出解的个数，然后从小到大输出解（最简分数形式）

分析：

就是模拟解方程的过程，先 解出$N$个$a_i?x+b_i$的零点$k_i$，然后排好序，得到$N+1$个区间：
$(?\infty ,k_1),[k_1,k_2),[k_2,k_3)\dots ,[k_{n?1},k_n),[k_n,+\infty )$

这样从右往左遍历区间，每次把对应的$a_i,b_i$变成负的（先以正的形式全部加上得到$suma,sumb$，之后再从里面减去2倍的$a_i,b_i$即可），再验证一下解出来的x是不是在这个区间里面就行。

对于无穷多个解的判断，$suma?x+sumb=C$，当$suma=0$且$C?sumb=0$时，有无穷多的解。注意，仅当$suma=0$的话只是在该区间无解，应当继续判断。

还要注意判断一下$k$相同的区间。

还有，排序的时候sort的cmp函数里面不要有 “=”，会出问题…

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e5+50;
const LL INF=0x3f3f3f3f;
LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}
struct frac
{
    LL up;LL down;bool friend operator <(const frac &x,const frac &y){
    return x.up*y.down<y.up*x.down;}bool friend operator ==(const frac &x,const frac &y){
    return x.up*y.down==y.up*x.down;}bool friend operator <=(const frac &x,const frac &y){
    return x.up*y.down<=y.up*x.down;}
};
struct node
{
    LL a;LL b;frac k;
}r[maxn];
bool cmp(const node &x,const node &y)
{
    return x.k<y.k;
}
frac create(LL a,LL b)
{
    LL t=gcd(abs(a),abs(b));frac x;x.up=a/t;x.down=b/t;if(x.down<0){
    x.up=-x.up;x.down=-x.down;}return x;
};
LL N,C;
frac ans[maxn],x;
int main()
{
    int T;scanf("%d",&T);while(T--){
    scanf("%lld %lld",&N,&C);LL suma=0,sumb=0,cnt=0;for(int i=1;i<=N;i++){
    scanf("%lld %lld",&r[i].a,&r[i].b);suma+=r[i].a;sumb+=r[i].b;r[i].k=create(-r[i].b,r[i].a);}sort(r+1,r+N+1,cmp);bool inf=false;cnt=0;r[0]=node{
    0,0,create(-INF,1)};r[N+1]=node{
    0,0,create(INF,1)};for(int i=N+1;i>=1;i--){
    suma-=2*r[i].a;sumb-=2*r[i].b;if(r[i].k==r[i-1].k)     //k值相同的区间continue;if(suma==0&&C-sumb==0)   //无穷解{
    inf=true;break;}elsex=create(C-sumb,suma);if(r[i-1].k<=x&&x<r[i].k)   //验证x∈[k[i-1],k[i])ans[cnt++]=x;}if(inf)printf("-1\n");else{
    printf("%d",cnt);for(int i=cnt-1;i>=0;--i)    //从小到大输出解printf(" %lld/%lld",ans[i].up,ans[i].down);printf("\n");}}return 0;
}