首页 > 代码库 > BNUOJ 36005 Chemical Reaction
BNUOJ 36005 Chemical Reaction
Chemical Reaction
Time Limit: 3000ms
Memory Limit: 65536KB
This problem will be judged on OpenJudge. Original ID: C14H64-bit integer IO format: %lld Java class name: Main
There are n chemical elements. Each of them has two attributes, a and b. When two different elements are mixed, a chemical reaction will occur. During a chemical reaction, energy will be released. The following expression tells the amount of energy that is released when i-th element and j-th element are mixed:
|ai - aj| ? bi ? bj / max(|bi|, |bj|)
Could you find the maximal energy that can be released by mixing two elements?
Note that the value of the expression may be negative, which means the chemical reaction absorbs energy. For simplicity, we regard it as releasing negative energy, so you can compare two values of the expression directly to determine which releases more energy.
Input
The first line contains an integer T (1 ≤ T ≤ 10) -- the number of test cases.
For each test case:
The first line contains an integer n. 2 ≤ n ≤ 500 000.
Then follows n lines, each line contains two integers: a, b, indicate the two attributes of a chemical element. 0 ≤ | a | ≤ 10 000. 1 < | b | ≤ 10 000.
For each test case:
The first line contains an integer n. 2 ≤ n ≤ 500 000.
Then follows n lines, each line contains two integers: a, b, indicate the two attributes of a chemical element. 0 ≤ | a | ≤ 10 000. 1 < | b | ≤ 10 000.
Output
For each test case, output one integer in a single line -- the maximal energy that can be released by mixing two elements.
Sample Input
151 5-2 43 75 -3-6 -2
Sample Output
22
解题：把b进行分类，负数的一边，正数的一边，然后就可以了。。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define INF 0x3f3f3f3f15 #define pii pair<int,int>16 using namespace std;17 const int maxn = 500100;18 struct node {19 int x,y,id,minv,maxv;20 node(int tx = 0,int ty = 0,int tz = 0) {21 x = tx;22 y = ty;23 id = tz;24 }25 bool operator< (const node &t)const{26 return y < t.y;27 }28 };29 node pa[maxn],pb[maxn];30 int ca,cb,u[maxn],v[maxn],T,n;31 int bsearch(int lt,int rt,int val,node *d){32 int ans = rt+1;33 while(lt <= rt){34 int mid = (lt+rt)>>1;35 if(d[mid].y >= val){36 ans = mid;37 rt = mid-1;38 }else lt = mid+1;39 }40 return ans;41 }42 int main() {43 scanf("%d",&T);44 while(T--) {45 scanf("%d",&n);46 for(int i = ca = cb = 0; i < n; ++i) {47 scanf("%d %d",u+i,v+i);48 if(v[i] < 0) pa[ca++] = node(u[i],-v[i],i);49 else pb[cb++] = node(u[i],v[i],i);50 }51 sort(pa,pa+ca);52 sort(pb,pb+cb);53 if(ca) pa[ca-1].minv = pa[ca-1].maxv = pa[ca-1].x;54 if(cb) pb[cb-1].minv = pb[cb-1].maxv = pb[cb-1].x;55 for(int i = ca-2; i >= 0; --i) {56 pa[i].minv = min(pa[i].x,pa[i+1].minv);57 pa[i].maxv = max(pa[i].x,pa[i+1].maxv);58 }59 for(int i = cb-2; i >= 0; --i) {60 pb[i].minv = min(pb[i].x,pb[i+1].minv);61 pb[i].maxv = max(pb[i].x,pb[i+1].maxv);62 }63 int ans = -INF;64 for(int i = 0; i < n; ++i) {65 int idx = INF;66 if(ca) {67 idx = bsearch(0,ca-1,abs(v[i]),pa);68 if(idx < ca && pa[idx].id == i) idx++;69 if(idx < ca) {70 ans = max(ans,-abs(u[i] - pa[idx].minv)*v[i]);71 ans = max(ans,-abs(u[i] - pa[idx].maxv)*v[i]);72 ans = max(ans,-abs(pa[idx].minv - u[i])*v[i]);73 ans = max(ans,-abs(pa[idx].maxv - u[i])*v[i]);74 }75 }76 if(cb) {77 idx = bsearch(0,cb-1,abs(v[i]),pb);78 if(idx < cb && pb[idx].id == i) idx++;79 if(idx < cb) {80 ans = max(ans,abs(u[i] - pb[idx].minv)*v[i]);81 ans = max(ans,abs(u[i] - pb[idx].maxv)*v[i]);82 ans = max(ans,abs(pb[idx].minv - u[i])*v[i]);83 ans = max(ans,abs(pb[idx].maxv - u[i])*v[i]);84 }85 }86 }87 printf("%d\n",ans);88 89 }90 return 0;91 }
BNUOJ 36005 Chemical Reaction
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。