题解 化学反应

化学反应

Description

有 N 种不同的物质，每种物质有两个属性——“能量”和“活度”。 N 种中的任意两种物质都可以发生反应；反应放热为两种物质的“能量”之差加一再乘上“活度”的较大值。换句话说，设第 i 种物质的能量和活度分别为 Ai 和 Bi，则 i 和 j 反应的放热为

现在你需要选出两种物质，最小化它们反应放出的热量。这个最小值是多少？

Input

本题包含多组测试数据，第一行为测试数据组数 T。
对于每组数据：
第一行一个正整数 N，表示物质种类数。
接下来 N 行每行两个正整数 Ai、 Bi，表示第 i 种物质的“能量”和“活度”。

Output

输出一行一个正整数，最小放热。 注意这个数可能需要 64 位整型来存储。

Sample Input

1
7
19 5
5 6
1 2
8 4
25 10
12 3
9 6

Sample Output

12

Hint

数据范围：
对于 40%的数据，N<=1000，T<=5
对于另外 20%的数据，N<=10^5，Ai、 Bi<=10^3，T=1
对于 100%的数据，N<=10^5，Ai、 Bi<=10^9，T<=40

Source

贪心，分治

解析

这题的解法非常的巧（qí）妙(pa)。

首先，暴力n² 肯定会炸！

所以，我们先以A为关键字从小到大排序（从小到大也可以）。

然后枚举每个物质i，

寻找离它最近且B不大于Bi的两个物质j1,j2.

因为最近，所以差肯定最小。

然后更新ans就行了。

然后就有人会问：

如果存在物质x,Bx>Bi且(abs(Ax-Ai)+1)*Bx（即热量）比上面的j1,j2更小。

那x岂不是被忽略了？

然而实际上，如果上面的方案真的可行的话，

那么在枚举到x时，答案就已经被更新了。

因此，就不用担心了。

最后，注意每组数据都要初始化ans(而且要大，我赋的是1e16)（爆零惨案）

上AC代码吧：

#include
#define ll long long
using namespace std;inline int read(){ll sum=0,f=1;char ch=getchar();while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return f*sum;
}struct node{ll a,b;
}c[100001];
int n,T;
ll ans=0x3f3f3f3f;bool cmp(node aa,node bb){return aa.a>bb.a;
}int main(){
//    freopen("reaction.in","r",stdin);
//    freopen("reaction.out","w",stdout);T=read();while(T--){ans=1e16;n=read();for(int i=1;i<=n;i++) c[i].a=read(),c[i].b=read();sort(c+1,c+n+1,cmp);for(int i=1;i<=n;i++){ll ret=1e16;ll a1=ret,a2=ret;int j=i-1;while(j>0){if(c[j].b<=c[i].b){a1=c[j].a;break;}j--;}j=i+1;while(j<=n){if(c[j].b<=c[i].b){a2=c[j].a;break;}j++;}if(a1==ret&&a2==ret) continue;ans=min(ans,(ll)(min(abs(a1-c[i].a),abs(c[i].a-a2))+1)*c[i].b);//    cout<<"ans="<
        }printf("%lld\n",ans);}return 0;
}

转载于:https://www.cnblogs.com/zsq259/p/10524804.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！