脚本宝典收集整理的这篇文章主要介绍了Cycle Function - 题解【二分】，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
这是2019四川省赛的C题。这里放上CodeForces的链接：C. Cycle Function - Codeforces
Fish is learning functions! He has a linear function (f(x)=Ax+B) and (N) numbers (x_1,x_2,⋯,x_N). Now he is curious about for each function (g(x)) in
[ left{ begin{matrix} g_1(x)=c_1x+d_1\ g_2(x)=c_2x+d_2\ vdots\ g_M(x)=c_Mx+d_M end{matrix} right} ]how to calculate the difference between (f(g(x))) and (g(f(x))).
As smart as Fish is, he soon comes up wITh a function (D(x)=|f(g(x))−x|+|g(f(x))−x|) and uses the sum over (x_1,x_2,⋯,x_N) as the difference.
Can you tell him all the differences immediately?
Input The First line of input contains an integer (T), rePResenting the number of test cases.
Then for each test case:
The first line contains two integers (N, M) as mentioned above and then two real numbers (A, B) indicating the given function (f(x)=Ax+B).
The second line contains (N) real numbers (x_1,x_2,⋯,x_N).
Then (M) lines follow, each line containing two real numbers (c_i, d_i) indicating a function (g_i(x)=c_ix+d_i) mentioned above.
All numbers in the same line are separated by one space.
Output For each test case, you should output
Case x:in the first line, where (x) indicates the case number starting From (1).Then (M) lines follow, the (i)-th line of which contains a real number representing the difference for given function (g_i(x)).
Your answers will be considered correct if its absolute error does not exceed (10^{−6}).
Limits
time limit PEr test: 5 seconds memory limit per test: 256 megabytes input: standard input output: standard output
Note
(1≤T≤100) (1≤N,M≤10^5) (−100≤A,B,x_i,c_i,d_i≤100) For (90%) test cases: (max(N,M)≤1000)
Example Input
2 3 2 2.0 3.0 1.0 2.0 3.0 0.4 -2.0 0.6 -5.0 3 2 2.5 2.0 1.0 2.0 3.0 0.4 -2.0 0.6 -5.0Example Output
Case 1: 7.800000 28.200000 Case 2: 12.600000 36.900000
给定一个线性函数(f(x)=Ax+B)和一个线性函数组(g_i(x)=c_ix+d_i)，定义函数(D(x)=|f(g(x))−x|+|g(f(x))−x|)，对于给定的一组数(x_i,enspace i=i,2,dots,n)，求关于线性函数组里的每个函数，$ sum_{i=1}^{n} D(x_i)$的值。
我们对这两个绝对值符号里面的内容做一下数学变换，记(Ac-1=a,Ad+B=p,Bc+d=q)：
式子变得简单了不少。但是绝对值仍然是一个让人非常讨厌的东西，需要对正数与负数进行分类讨论。而且，本题有至多1e5个变量和 1e5个函数，虽然时间限制是5秒，但是平方复杂度的暴力解法必定会超时。我们考虑到，对于线性函数(F(x)=kx+b)，当(k=0)时值永远为(b)，否则其零点为(x_0=-frac{b}{k})，因此我们只需要特判系数(a)是否为0，然后考虑大于(x_0)的数以及不大于(x_0)的数，分别计算即可，一连串数据的求和可以使用前缀和来维护，分界点排序后使用二分查找函数lower_bound即可。这题知道思路了就很简单，但是确实蛮难想的……
排序复杂度为(O(NLOGN))，对每个函数二分查找总复杂度为(O(MLogN))，综合复杂度为(O((M+N)logN))，可以接受。
另：本题卡输入输出，要使用C风格的输入输出或者手搓快读快写。Java或者Python选手还是放弃吧o(￣▽￣)ブ笔者使用关闭流同步的cincout超时，改scanfprintf只用了2000ms……
下面是代码：
#include <bits/stdc++.h>
#define GRP int T;cin>>T;rep(C,1,T)
#define FAST ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define elif else if
#define mem(arr,val) memset(arr,val,sizeof(arr))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const double EPS = 1e-8;
int n, m;
double a, b;
double xs[100010], x[100010], c, d;
double ans;
int main() {
xs[0] = 0;
GRP {
scanf("%d %d %lf %lf", &n, &;m, &a, &b);
printf("Case %d:n", C);
//读入并排序，求前缀和
rep(i, 1, n) {
scanf("%lf", x + i);
}
sort(x + 1, x + 1 + n);
rep(i, 1, n) {
xs[i] = xs[i - 1] + x[i];
}
//处理每个g(x)
rep(i, 1, m) {
scanf("%lf %lf", &c, &d);
ans = 0;
double a1 = a * c - 1, p = a * d + b, q = b * c + d; //计算系数
if (abs(a1) < EPS) { //浮点数为0应判断其绝对值小于一个极小值
ans = (abs(p) + abs(q)) * n;
} else {
//寻找分界点
int i1 = lower_bound(x + 1, x + 1 + n, -p / a1) - x - 1;
int i2 = lower_bound(x + 1, x + 1 + n, -q / a1) - x - 1;
//分别求值并且累加
ans += abs(a1 * (xs[i1] - xs[0]) + p * (i1));
ans += abs(a1 * (xs[n] - xs[i1]) + p * (n - i1));
ans += abs(a1 * (xs[i2] - xs[0]) + q * (i2));
ans += abs(a1 * (xs[n] - xs[i2]) + q * (n - i2));
}
printf("%.7lfn", ans);
}
}
return 0;
}
/*
_ _ _ _
/ | | | | | | (_)
/ | | _____ _| |__| | ___ _ __ _ _ __ __ _
/ / | |/ _ / / __ |/ _ | '__| | '_ / _` |
/ ____ | | __/> <| | | | (_) | | | | | | | (_| |
/_/ __|___/_/__| |_|___/|_| |_|_| |_|__, |
__/ |
|___/
*/
以上是脚本宝典为你收集整理的Cycle Function - 题解【二分】全部内容，希望文章能够帮你解决Cycle Function - 题解【二分】所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。