134 条题解
-
5
PowderHan LV 10 @ 2016-08-14 13:46:49
/* 我去，这题恶心啊。 基本思路，从小到大快排，然后对于每个a[i],除以个黄金比例可以得出一个正好完美的数， 再用这个数去二分查找数列中找最近的数，再用找到这个数去除以a[i]， 得出的比例要与黄金比例最接近。 1.精度问题：黄金比例一定要直接按题目的来。不要就保留前几位orz 2.查找问题：可能是我太弱了，一直错在查找这个地方。二分查找返回下标。 这个下标到底选哪个好呢？又不是找相等+浮点数 这就比较尴尬了，然后弱逼的我是一开始直接返回l-1，结果呵呵哒一直有一个点过不去呀， 然后我就l,l-1,l+1三个比较一遍取最优的返回，结果就特么过了？ 发现自己还是太不细心加做题少啊，弱逼一枚 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const double xyz=0.6180339887498949; int n; double a[30005]; double ans=9999999999.0; int x,y; int search(double e,int p) { int l=p+1,r=n; while(l<=r) { int mid=(l+r)/2; if(a[mid]<=e) l=mid+1; else r=mid-1; } double w=fabs(a[l]-e); double b=fabs(a[l-1]-e); double c=fabs(a[l+1]-e); if(w<b&&w<c) return l; else if(b<w&&b<c) return l-1; else return l+1; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); for(int i=1;i<=n;i++) { double t=(a[i]/(xyz)); int k=search(t,i); double temp=fabs(a[i]/a[k]-xyz); if(temp<ans) { ans=temp; x=a[i]; y=a[k]; } } cout<<x<<endl<<y<<endl; return 0; } -
3
简单的二分
手写了一下abs#include<iostream> #include<algorithm> #include<cmath> const double N=0.6180339887498949; using namespace std; int a[30010]; double aabs(double x) { if(x>0) return x; return -x; } int main() { int n,i,l,r,mid,ans,z,y; double minn=100000.0,ha; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); for(i=1;i<n;i++) { l=i+1; r=n; while(l<=r) { mid=(l+r)/2; ha=double(a[i])/(double(a[mid])); //cout<<l<<" "<<r<<" "; // cout<<ha<<endl; if(aabs(ha-N)<aabs(minn-N)) { minn=ha; z=a[i]; y=a[mid]; } if(ha<N) r=mid-1; else l=mid+1; } } cout<<z<<endl<<y; return 0; } -
3
Accepted
状态 耗时 内存占用
#1 Accepted 1ms 256.0 KiB
#2 Accepted 1ms 256.0 KiB
#3 Accepted 24ms 372.0 KiB
#4 Accepted 27ms 328.0 KiB
#5 Accepted 24ms 388.0 KiB
#6 Accepted 27ms 196.0 KiB
#7 Accepted 29ms 360.0 KiB
#8 Accepted 23ms 256.0 KiB
#9 Accepted 23ms 256.0 KiB
#10 Accepted 26ms 324.0 KiB
代码
const p=0.6180339887498949;
var
a:array[0..30001]of longint;
n,i,x,y:longint;
min:real;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do
inc(i);
while x<a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure search(l,r:longint);
var
m:longint;
k:real;
begin
m:=a[(l+r) div 2];
k:=abs(a[i]/m-p);
if k<min then begin min:=k; x:=a[i]; y:=m; end;
if l>=r then exit;
if r-l=1 then begin
if abs(a[i]/a[r]-p)<min then begin min:=abs(a[i]/a[r]-p); x:=a[i]; y:=a[r]; end;
exit;
end;
if a[i]/m<p then search(l,(l+r) div 2);
if a[i]/m>p then search((l+r) div 2,r);
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
readln;
sort(1,n);
min:=maxlongint;
for i:=1 to n-1 do
search(i+1,n);
writeln(x);
writeln(y);
end. -
2
这个题目告诉我们做题要大胆，只要敢做强制类型转换也没问题的
// #if 1 //INCLUDE HEADERS #include <iostream> #include <algorithm> #include <string> #include <string.h> #include <cstdio> #include <cstdlib> #include <cmath> #include <map> #include <set> #include <list> #include <queue> #include <stack> #include <vector> #include <memory.h> #include <sstream> //MACROS #define ll long long #define MAX 65535 #define pause system("pause"); #define debug printf("__DEBUG__\n"); using namespace std; #define sigma 0.6180339887498949 int main() { int n; cin >> n; vector<double>v; int x; for (int i = 0; i < n;++i) { cin >> x; v.push_back(x); v.push_back(x*sigma); } sort(v.begin(), v.end()); int j = 0; double min = MAX; for (unsigned i = 1; i < v.size();++i) { if (v[i]-v[i-1]<min) { if ((int(v[i])==v[i])^(int(v[i-1])==v[i-1])) { min = v[i] - v[i - 1]; j = i; } } } if (int(v[j])==v[j]) { cout << v[j] <<endl << int(v[j - 1] / sigma) << endl; } else { cout << v[j - 1] << endl << int(v[j] / sigma) << endl; } return 0; } #endif -
2
写了个奇奇怪怪的东西233
把所有长度和0.618倍长度一起排序，距离最近的就是答案
不加1e-10得90，加了终于ac#include<iostream> #include<stdlib.h> #include<stdio.h> #include<string.h> #include<limits.h> #include<math.h> #include<algorithm> #include<string> #include<queue> #include<vector> #include<map> #include<set> #include<bitset> #include<iomanip> using namespace std; long double g=0.6180339887498949; inline long double myabs(long double x){return((x>0.0)?x:-x);} inline bool eq(long double x,long double y){return((myabs(x-y)<1e-8)?1:0);} inline int sgn(long double x){if(!eq(x,0.0)){if(x>0) return 1;else return -1;} else return 0;} int comp0(const void *a,const void *b){return sgn(((double)(((long double *)a)[0])-(double)(((long double *)b)[0])));} int main_wa() { int n,t=0,c=0;cin>>n;long double l[2*n+2][2];int lb[n+1]; for(int i=0;i<n;i++){cin>>lb[i+1];if(lb[i+1]){l[t][0]=lb[i+1];l[t][1]=i+1;t++;l[t][0]=l[t-1][0]*g;l[t][1]=-l[t-1][1];t++;}} if(!t){cout<<0<<endl<<0<<endl;return 0;} if(t==2){cout<<0<<endl<<l[0][0]<<endl;return 0;} qsort(l,t,2*sizeof(long double),comp0); long double min=1e6;long long int ia=1e6,ib=1e6; for(int i=1;i<t;i++) { if((((myabs(l[i][0]-l[i-1][0])/l[i-1][0])<min)||(eq((myabs(l[i][0]-l[i-1][0])/l[i-1][0]),min)&&(myabs(l[i][0]*l[i-1][0])<lb[ia]*lb[ib]*g)))&&(!eq(l[i][1]+l[i-1][1],0.0))&&(l[i][1]*l[i-1][1]<0)) {min=(myabs(l[i][0]-l[i-1][0])/l[i-1][0]);ia=myabs(l[i][1])+1e-6;ib=myabs(l[i-1][1])+1e-6; if(lb[ia]>lb[ib]) {c=ia;ia=ib;ib=c;}} }cout<<lb[ia]<<endl<<lb[ib]<<endl; return 0; } int main() { int n,t=0,c=0;cin>>n;long double l[2*n+2][2];int lb[n+1]; for(int i=0;i<n;i++){cin>>lb[i+1];if(lb[i+1]){l[t][0]=lb[i+1];l[t][1]=i+1;t++;l[t][0]=l[t-1][0]*g;l[t][1]=-l[t-1][1];t++;}} if(!t){cout<<0<<endl<<0<<endl;return 0;} if(t==2){cout<<0<<endl<<l[0][0]<<endl;return 0;} qsort(l,t,2*sizeof(long double),comp0); long double min=1e6;long long int ia=1e6,ib=1e6; for(int i=1;i<t;i++) { if((((myabs(l[i][0]-l[i-1][0])/l[i-1][0])+jd<min)||(eq((myabs(l[i][0]-l[i-1][0])/l[i-1][0]),min)&&(myabs(l[i][0]*l[i-1][0])<lb[ia]*lb[ib]*g)))&&(!eq(l[i][1]+l[i-1][1],0.0))&&(l[i][1]*l[i-1][1]<0)) {min=(myabs(l[i][0]-l[i-1][0])/l[i-1][0]);ia=myabs(l[i][1])+1e-6;ib=myabs(l[i-1][1])+1e-6; if(lb[ia]>lb[ib]) {c=ia;ia=ib;ib=c;}} }cout<<lb[ia]<<endl<<lb[ib]<<endl; return 0; }
真是怀念啊...
现在还有两个月高考之际，回顾我高一时写的惨不忍睹的码（虽然之后去搞ChO然后Cu了）
大一打卡。
作为竞赛生的日子...真好啊。 -
2
uses math; const p=0.6180339887498949; var a:array[0..30001] of longint; w:array[1..2] of longint; n,i:longint; procedure qsort(b,e:longint); var temp,x,i,j:longint; begin if b<e then begin x:=random(e-b)+b; temp:=a[x];a[x]:=a[e];a[e]:=temp; x:=a[e];i:=b-1; for j:=b to e-1 do if a[j]<x then begin inc(i); temp:=a[j];a[j]:=a[i];a[i]:=temp; end; a[e]:=a[i+1];a[i+1]:=x; qsort(b,i); qsort(i+2,e); end; end; procedure bin(i:longint); var lb,ub,mid:longint;k:extended; begin lb:=i;ub:=n+1; k:=a[i]/p; while (ub-lb)>1 do begin mid:=(lb+ub) div 2; if a[mid]>=k then ub:=mid else lb:=mid; end; if (ub<n+1) and (abs(a[i]/a[ub]-p)<abs(w[1]/w[2]-p)) then begin w[1]:=a[i]; w[2]:=a[ub]; end; if (lb>i) and (abs(a[i]/a[lb]-p)<abs(w[1]/w[2]-p)) then begin w[1]:=a[i]; w[2]:=a[lb]; end; end; begin randomize; read(n); for i:=1 to n do read(a[i]); qsort(1,n); w[1]:=a[1];w[2]:=a[2]; for i:=1 to n do bin(i); writeln(w[1]); writeln(w[2]); end. -
1
//
#if 1//INCLUDE HEADERS
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <memory.h>
#include <sstream>
//MACROS
#define ll long long
#define MAX 65535
#define pause system("pause");
#define debug printf("__DEBUG__\n");
using namespace std;#define sigma 0.6180339887498949
int main() {
int n;
cin >> n;
vector<double>v;
int x;
for (int i = 0; i < n;++i)
{
cin >> x;
v.push_back(x);
v.push_back(x*sigma);
}
sort(v.begin(), v.end());int j = 0;
double min = MAX;
for (unsigned i = 1; i < v.size();++i)
{
if (v[i]-v[i-1]<min)
{
if ((int(v[i])==v[i])^(int(v[i-1])==v[i-1]))
{
min = v[i] - v[i - 1];
j = i;
}
}
}
if (int(v[j])==v[j])
{
cout << v[j] <<endl << int(v[j - 1] / sigma) << endl;
}
else {
cout << v[j - 1] << endl << int(v[j] / sigma) << endl;
}return 0;
}#endif
-
1
我的思路：左边的数从i开始，右边的数从i+1到n-1结束。然后二分搜索右边的数。
#include<iostream>
#include<algorithm>
using namespace std;
int n,base,mid,right1,left1,saveleft,saveright,flag,add=70000;
double stand =0.6180339887498949,temp,dis;
int data[40000]={0};
double divv2=10000000;
int myabs(double divv)
{
if(divv <stand)
{
return -1;
}
else return 1;
}
double myabs2(double divv)
{
if(divv>stand) return divv-stand;
else return stand -divv;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin >>data[i];
sort(data,data+n);
for(int i=0;i+1<n;i++)
{
base=i;
left1=i+1;
right1=n-1;
mid=(left1+right1) >>1; //得到了位置
while(left1<=right1)
{
dis=(double)data[base] / data[mid];
dis=myabs2(dis);
if(dis<divv2)
{
//cout <<data[base]<<" " <<data[mid] <<endl;
divv2=dis;
saveleft=base,saveright=mid;
}
flag =myabs((double)data[base]/data[mid]);
if(flag==-1)
{
right1=mid-1;
}
else
{
left1=mid+1;
}
mid=(left1+right1) >>1;
}
}
cout <<data[saveleft]<<endl << data[saveright];
return 0;
} -
1
说真的，这题没什么难度，没用二分照样过了……思路是先排一遍序；再把每个数乘黄金比的值算出来，最后找2个差最小的数，输出，结束
```cpp
//#include "stdafx.h"
#include<bits/stdc++.h>
using namespace std;
const double golden = 0.6180339887498949;
int n, x[30009],f,s;
double goal[30009],minn=100000.000000000000000;int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++)
cin >> x[i];
sort(x, x + n);
for (int i = 0; i < n; i++)
{
goal[i] = double(x[i])*golden;}for(int i=0;i<n;i++){
for(int j=i-1;j>=0;j--)
if (abs(double(x[j] )- goal[i])< minn)
{
minn = abs(double(x[j])- goal[i]);
f = x[i];
s = x[j];
}}
cout << s <<endl<< f;
//system("pause");
return 0;
}
```-
ys3330068 @ 2017-08-19 10:59:18
一开始的数据不就是有序的么
-
-
1
MarkAllenWeiss LV 8 @ 2016-11-08 20:44:51
为何我会RE。。。。help
#include <stdio.h>
void Qsort (long l,long r,long s[]);
double analys(long ,long );
void Swap(long *a,long *b);
int main()
{
int N,n=0,m=0;
long a,b;
double tmp,min=10,P=0.6180339887498949;
long input[30000];
scanf("%d",&N);
for (n=0;n<N;n++)
scanf("%ld",&input[n]);
Qsort(0,N-1,input);
while (input[n]==0) n++;
for (n=0;n<N-1;n++)
for (m=n+1;m<N;m++)
{
tmp=analys(input[n],input[m]);
if ((tmp-P)>=0) tmp-=P;
else tmp=P-tmp;
if (tmp<min)
{
min=tmp;
a=input[n];
b=input[m];
}
}
printf("%ld\n%ld\n",a,b);
return 0;
}
double analys(long a,long b)
{
return (double)(a/b);
}
void Swap(long *a,long *b) //无需添加新变量
{
(*a)+=(*b);
(*b)=(*a)-(*b);
(*a)-=(*b);
}
void Qsort (long l,long r,long s[]) //最终结果为升序数列
{
long mid=(l+r)/2,n=l,m=r-1,pivot;
if ((r-l)==1)
{
if (s[r]<s[l]) Swap(&s[l],&s[r]);
}
else
{
if (s[l]>s[mid]) Swap(&s[l],&s[mid]);
if (s[l]>s[r]) Swap(&s[l],&s[r]);
if (s[mid]>s[r]) Swap(&s[r],&s[mid]);
pivot=s[mid];
Swap(&s[mid],&s[m]);
for (;;)
{
while (s[++n]<pivot) ;
while (s[--m]>pivot) ;
if (n<m) Swap(&s[n],&s[m]);
else break;
}
Swap(&s[n],&s[r-1]);
Qsort(l,n,s);
Qsort(n+1,r,s);
}
} -
0
//我直接用stl中的lower_bound过掉了耶
#include<bits/stdc++.h> #define V (to[i]) #define debug printf("%d %s\n",__LINE__,__FUNCTION__) #define PP system("pause") #define N 1000010 #define NN 2010 #define NNN 310 #define eps 1e-18 using namespace std; namespace program { #define gc() getchar() #define pc putchar inline long long read(){ register long long x=0,f=1;register char c=gc(); for(;!isdigit(c);c=gc())if(c=='-')f=-1; for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48); return x*f; } inline void write(long long x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');} inline void writeln(long long x){write(x);puts("");} int n,id1,id2; const long double hjb=0.6180339887498949; long double ans=999999999999999.99999999,a[30030]; inline void work() { n=read(); for(int i=1;i<=n;i++) scanf("%Lf",&a[i]); sort(a+1,a+n+1); for(int i=1;i<n;i++) { long double now=a[i]/hjb; int oo=lower_bound(a+1,a+n+1,now)-a; long double sum1=a[i]/a[oo]; long double sum2=a[i]/a[oo-1]; long double sum3=a[i]/a[oo+1]; if(abs(sum1-hjb)<abs(ans-hjb)) { ans=sum1; id1=i; id2=oo; } if(abs(sum2-hjb)<abs(ans-hjb)) { ans=sum2; id1=i; id2=oo-1; } if(abs(sum3-hjb)<abs(ans-hjb)) { ans=sum3; id1=i; id2=oo+1; } } writeln(a[id1]); writeln(a[id2]); } } int main() { freopen("gaojunonly1.in","r",stdin); program::work(); return 0; } -
0
1559896546 LV 7 @ 2016-07-24 18:36:31
有0。。。。。注意了就好了，标记上两个指针，搜就好了
-
0
/* *********************************************** Author :guanjun Created Time :2016/3/26 10:24:40 File Name :vijos1237.cpp ************************************************ */ #include <iostream> #include <cstring> #include <cstdlib> #include <stdio.h> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <iomanip> #include <list> #include <deque> #include <stack> #define ull unsigned long long #define ll long long #define mod 90001 #define INF 0x3f3f3f3f #define maxn 30010 #define cle(a) memset(a,0,sizeof(a)) const ull inf = 1LL << 61; const double eps=0.6180339887498949; using namespace std; priority_queue<int,vector<int>,greater<int> >pq; struct Node{ int x,y; }; struct cmp{ bool operator()(Node a,Node b){ if(a.x==b.x) return a.y> b.y; return a.x>b.x; } }; bool cmp(int a,int b){ return a>b; } double a[maxn]; int main() { #ifndef ONLINE_JUDGE // freopen("in.txt","r",stdin); #endif //freopen("out.txt","w",stdout); int n; while(cin>>n){ for(int i=1;i<=n;i++)scanf("%lf",&a[i]); sort(a+1,a+n+1); double ans=1000000; ll ans1,ans2; for(int i=1;i<n;i++){ int y=ceil(a[i]*1.0/eps+0.5); int x=lower_bound(a+i+1,a+n+1,y)-a-1; double tmp=fabs((double)a[i]/(double)a[x]-eps); if(tmp<ans){ ans=tmp; ans1=a[i]; ans2=a[x]; } } cout<<ans1<<endl<<ans2<<endl; } return 0; } -
0
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double gold = 0.6180339887498949;
const int MAXN = 1000000;int to;
int num[MAXN];int search(int a, int b){
if(a == b)
return a;
int div = (a + b) / 2, flag;
if(num[div] >= to){
flag=search(a, div);
if(abs(num[div+1]-to) < abs(num[flag]-to))
flag = div + 1;
}
else{
flag=search(div+1, b);
if(abs(num[div]-to) < abs(num[flag]-to))
flag = div;
}
return flag;
}double fabs(double x){
if(x >= 0)
return x;
else
return -x;
}int main()
{
int n, ans1, ans2;
double bri = 1000000;
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &num[i]);
sort(&num[1], &num[1]+n);
for(int i=1; i<n; i++){
to = (int)round(num[i] / gold);
int u = search(i+1, n);
double v = fabs( (double)num[i]/(double)num[u] - gold );
if(v < bri){
bri = v;
ans1 = num[i];
ans2 = num[u];
}
}
printf("%d\n%d\n", ans1, ans2);
system("pause");
return 0;
}
求指导，，共同进步 -
0
Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步 -
0
评测结果
编译成功foo.cpp: In function 'int find(double)':
foo.cpp:8:12: warning: unused variable 'd' [-Wunused-variable]
测试数据 #0: Accepted, time = 0 ms, mem = 648 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 648 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 652 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 656 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 652 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 656 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 656 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 656 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 648 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 652 KiB, score = 10
Accepted, time = 136 ms, mem = 656 KiB, score = 100
代码
#include<cstdio>
#include<algorithm>
double abs(double a) { if (a>0) return a; else return -a;}
double min=1,gold=0.6180339887498949;
int n,l[30010],a,b;
int find(double flag) {
int ll=1,rr=n,m;
double d;
while (ll+1<rr) {
m=(ll+rr)/2;
if (l[m]>=flag) rr=m;
else ll=m;
} if (abs(l[ll]-flag)>abs(l[rr]-flag)) return rr;
else return ll;
}
int main(){
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%d",&l[i]);
std::sort(l+1,l+1+n);
for (int i=1; i<=n; i++) {
int j=find(l[i]/gold);
double d=l[i];d/=l[j];
if (abs(d-gold)<min) {
min=abs(d-gold);
a=i; b=j;
}
} printf("%d\n%d",l[a],l[b]);
}
PowderHan
LV 10
@ 2016-08-14 13:46:49
