「Wdsr-2」Pour Water - 题解

· · 题解

子任务 1

子任务 2

结论是：混合后温度最高的一杯水，混合前的两杯中必定有原先温度最高的一杯。

证明

贪心参考代码（By chenxinyang2006）：

#include <cstdio>
#include <algorithm>
#define ll long long
int n,k;
int cnt;
struct node{
    ll a,c;
}Q[1000005],now[1000005];

bool cmp(node a,node b){
    if(a.c == b.c) return a.a < b.a;
    return a.c > b.c;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++){
        scanf("%lld%lld",&Q[i].a,&Q[i].c);
    }
    std::sort(Q + 1,Q + n + 1,cmp);
    double mx = 0,tmp;
    for(int i = 2;i <= n;i++){
        tmp = (Q[1].a * Q[1].c + Q[i].a * Q[i].c) * 1.0 / (Q[1].a + Q[i].a);
        if(mx < tmp) mx = tmp;
    }
    printf("%.3f\n",mx);
    return 0;
}

综合以上算法，可以获得 50 分。

子任务 3

思路

注意到是求 k 大，那么求 k 大实际上只有两种方式：

  1. 通过求 1 大，2 大，3 大 …… 直到求出 k 大。
  2. 二分答案，然后数个数。

注意到 k 是 10^{10} 级别的，所以肯定选第二种了。

设当前二分的值为 v，那么我们要求的是数对 (i,j)，满足 1 \le i < j \le n,\dfrac{a_i \times c_i + a_j \times c_j}{a_i +a_j} \ge v 的数量

显然，a_i+a_j>0，所以变形得到

a_i \times c_i + a_j \times c_j \ge v \times a_i + v \times a_j

将含 i,j 的项分别放到左边，右边，得到：

a_i \times c_i - v\times a_i \ge v \times a_j - a_j \times c_j

发现两边的值都是确定的，我们分别算出。

然后就是这样一个问题了：

给出两个长度为 n 的序列 \{a_n\},\{b_n\}，你需要求出有多少对 (i,j)，满足 a_i \ge b_j。

这是一个经典问题，比较简单的一个做法是将两个序列分别排序，然后使用双指针法 O(n) 数出对数。

时间复杂度：O(n\log v\log n)。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std; 
#define ll long long
#define eps 1e-3
int n;
ll k;
int a[100005],c[100005];//a 毫升,c 温度 
double p[100005],q[100005];

bool cmp(double a,double b){
    return a < b;
} 

int check(double v){
    ll tot = 0;
    for(int i = 1;i <= n;i++){
        double x = a[i] * 1.0 * c[i],y = v * a[i]; 
        p[i] = x - y;
        q[i] = y - x; 
        if(q[i] - p[i] < eps) tot--;
    }
    sort(p + 1, p + n + 1, cmp);
    sort(q + 1, q + n + 1, cmp);
    int j = 0;
    for(int i = 1;i <= n;i++){
        while((q[j + 1] - p[i]) < eps && j + 1 <= n) j++;
        tot += j;
    }
    return (tot / 2 < k);
}

int main(){
    scanf("%d%lld", &n, &k);
    for(int i = 1;i <= n;i++){
        scanf("%d%d",&a[i],&c[i]);
    }
    double l = 1,r = 1000000000,mid;
    while((r - l) > eps){
        mid = (l + r) / 2;
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid;
        }
    }
    printf("%.3f\n", l);
    return 0;
}