今天实在是有点蛋痛啊。。
开始复习一下二分搜索的题目。其实这个知识点，很早之前就应该掌握的了。。 到现在才开始，有点小郁闷啊。
如果有意想要做二分的朋友，建议先去练练手，做一做2141、2199，都是不错的练手二分题目。
此题目的意思，相信大家应该都懂，就是拿炮弹来堆三角形，然后告诉你有多少个这样的炮弹，你要告诉他现在一共有多少堆这样的三角形，然后告诉他最后一颗炮弹在最后一个三角形的行和列。。
其实就是生成两个基本的数组，然后用二分来搜索。。
这个两个数组就是
1、3、6、10....
1、4、10、20....
相信这个还是不用我多解释了。。
View Code 1 #include<iostream> 2 #include<stdio.h> 3 #include<math.h> 4 #define N 2002000 5 using namespace std; 6 __int64 sum[N],num[N],s,total,Count; 7 int search(__int64 n) 8 { 9 int left=0,right=N-1; 10 if(n<=sum[0])return 0; 11 while(left<right) 12 { 13 int mid=(left+right)/2; 14 if(sum[mid]>=n&&sum[mid-1]<n)return mid; 15 if(sum[mid+1]>=n&&sum[mid]<n)return mid+1; 16 if(sum[mid]>n)right=mid-1; 17 else 18 left=mid+1; 19 } 20 return left; 21 } 22 int search2(__int64 n,int m) 23 { 24 int left=0,right=m; 25 if(n<=num[0])return 0; 26 while(left<right) 27 { 28 int mid=(left+right)/2; 29 if(num[mid]>=n&&num[mid-1]<n)return mid; 30 if(num[mid+1]>=n&&num[mid]<n)return mid+1; 31 if(num[mid]>n)right=mid-1; 32 else 33 left=mid+1; 34 } 35 return left; 36 } 37 int main() 38 { 39 int t; 40 scanf("%d",&t); 41 total=0,Count=0; 42 __int64 k; 43 for(int i=1;i<=N;i++) 44 { 45 total+=i; 46 num[i-1]=total; 47 Count+=total; 48 sum[i-1]=Count; 49 } 50 while(t--) 51 { 52 scanf("%I64d",&s); 53 int pos=search(s); 54 int row=search2(s-sum[pos-1],pos); 55 int column; 56 if(row==0)column=1; 57 else 58 column=s-sum[pos-1]-num[row-1]; 59 printf("%d %d %d\n",pos+1,row+1,column); 60 } 61 return 0; 62 } 63
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667070.html
