贡献法贪心

题目传送门

N题

大致思路

比较相邻两个操作对答案的贡献,记下标 $i,j$
$i$的贡献:$a_j(a_i*x+b_i)+b_j$
$j$的贡献:$a_i(a_j*x+b_j)+b_i$
即比较 $a_j*b_i+b_j$ 和 $a_i*b_j+b_i$
写一个自定义排序即可,注意 $a==1$ 和 $a==0$要特判(放在最前面)

Code

bool cmp (const array<int,2> &a,const array<int,2> &b) {
    if (a[0]==0 && b[0]==0)return a[1]<b[1];
    if (a[0]==0) return true;
    if (b[0]==0) return false;
    if (a[0]==1) return true;
    if (b[0]==1) return false;
    int t1=a[0]*b[1]+a[1];
    int t2=b[0]*a[1]+b[1];
    return t1<t2;
}

void solve() {
    //a_j*b_i+b_j
    //a_i*b_j+b_i
    const int mod=1e9+7;
    int n;
    cin >> n;
    vector<array<int,2>> a(n);
    for (int i=0;i<n;i++) cin >> a[i][0] >> a[i][1];
    sort(all(a),cmp);
    int x=0;
    for (int i=0;i<n;i++) {
        x=(x*a[i][0])%mod+a[i][1];
        x%=mod;
    }
    cout << x<<el;
}