2 solutions
-
1
我们将一个人的成绩对应到三维空间中的位置向量,,一种排名的计算步骤被抽象为
- 确定一个法向量, 这个法向量需要满足这些条件:
- 指向第一卦限()
- $\text{GPA}_i=v[0]p[0]+v[1]p[1]+v[2]p[2]=\vec v \cdot \vec p_i$,随后就可以得到小林排名。
为什么这里不需要限制呢?这是因为只要,计算出来的GPA只是等比例放大缩小,不影响排名。
设小林的位置向量是,利用当作平面的法向量,可以确定一个过点的平面(关于的函数)。
虽然千变万化,但是我们并不需要考虑那么多的情况,实际上我们只需要考虑:
- 经过包括点的至少三个点
设表示如果确定平面是,小林的排名是多少,我们发现使得小林排名最高的中,一定至少有一个经过了包括点的至少三个点,即"临界条件"(使得变化)。
而还有三个临界条件,分别就是。
此时算法就有了,枚举两个点,法向量就是(或者),然后计算所有人的GPA得到小林的排名。记得把这几种情况考虑进去。
维的情况也有对应的的算法。这启示我们一件事,确定评价标准是一个非常主观的事情,可以让你高也让你低。所以最重要的还是是学到真正的本事。
#ifndef H1__ #define H2__ #include<bits/stdc++.h> using namespace std; int qr(){ int ret=0,c=getchar(); while(!isdigit(c)) c=getchar(); while( isdigit(c)) ret=ret*10+c-48,c=getchar(); return ret; } using ll = long long; int n; const int maxn=5050+5; struct NODE{ ll x,y,z; NODE():x(),y(),z(){} NODE(const ll&a,const ll&b,const ll&c):x(a),y(b),z(c){} NODE(const NODE&a):x(a.x),y(a.y),z(a.z){} NODE operator - (const NODE&a)const{ return NODE(x-a.x,y-a.y,z-a.z); } NODE operator - ()const{ return NODE(-x,-y,-z); } NODE operator % (const NODE&a)const{ const ll&X=a.x; const ll&Y=a.y; const ll&Z=a.z; return NODE(y*Z-z*Y,-x*Z+z*X,x*Y-y*X); } long long operator * (const NODE&a)const{ return x*a.x+y*a.y+z*a.z; } long long&operator[](const int&a){ assert(0<=a&&a<=2); if(a==0) return x; else if(a==1) return y; else return z; //impossible case } NODE&operator = (const NODE&a){ x=a.x; y=a.y; z=a.z; return *this; } }dat[maxn]; int calc(NODE normal){ if(normal[0]<0||normal[1]<0||normal[2]<0) normal=-normal; if(normal[0]<0||normal[1]<0||normal[2]<0) return n; if(normal*normal==0) return n; ll proj=normal*dat[1]; int cnt=0; for(int t=2;t<=n;++t) if(normal*dat[t]<=proj) ++cnt; return n-cnt; } int main(){ n=qr(); for(int t=1;t<=n;++t){ #ifdef H1__ int x=qr(),y=qr(),z=0; #else int x=qr(),y=qr(),z=qr(); #endif dat[t]=NODE(x,y,z); } NODE vec=dat[2]-dat[1]; int f=1; for(int t=2;t<=n;++t) if(vec%(dat[t]-dat[1])*(vec%(dat[t]-dat[1]))) f=0; // if(vec[0]>=0&&vec[1]>=0&&vec[2]>=0) return cout<<n<<endl,0; // vec=-vec; // if(vec[0]>=0&&vec[1]>=0&&vec[2]>=0) return cout<<n<<endl,0; if(f) return puts("1"),0; #ifdef H1__ NODE v2=NODE(0,0,1); int ans=n; for(int t=2;t<=n;++t){ NODE v1=dat[t]-dat[1]; NODE normal=v1%v2; //cerr<<normal[0]<<' '<<normal[1]<<endl; ans=min(ans,calc(normal)); } //cerr<<"H1__"<<endl; #else int ans=n; for(int t=2;t<=n;++t){ for(int i=2;i<=n;++i){ NODE v1=dat[t]-dat[1],v2=dat[i]-dat[1]; NODE normal=v1%v2; //cerr<<normal[0]<<' '<<normal[1]<<endl; //cerr<<v1[0]<<' '<<v1[1]<<' '<<v1[2]<<endl; ans=min(ans,calc(normal)); } } //cerr<<"!H1__"<<endl; #endif ans=min({ans,calc({1,0,0}),calc({0,1,0}),calc({0,0,1})}); cout<<ans<<endl; return 0; } #undef H1__ #endif
-
0
emmm……我看1≤n≤450,要不这道题暴力破解好了…… 我们以0.01为精度,依次枚举各部分分数占比,这样就能得到小林的最高排名了。 显然这也是一个O(n^3)的算法。 考虑到float乘int会比int乘int慢一些(如有不对请指出),我们枚举时会将
for(float i=0.00;i<=1.00;i+=0.01)
改写为for(int i=0;i<=100;++i)
。 代码见下:#include<bits/stdc++.h> using namespace std; int n,ans; int c1,c2; struct node{ bool b; int x,y,z; int all; }scr[451]; bool cmp(node a,node b){ if(a.all>b.all) return true; if(a.all==b.all&&b.b==true) return true; return false; } int main(){ scanf("%d",&n); scr[1].b=true; for(int i=1;i<=n;++i){ scanf("%d%d%d",&scr[i].x,&scr[i].y,&scr[i].z); } ans=450; for(c1=0;c1<=100;c1++){ for(c2=0;c2<=100-c1;c2++){ for(int i=1;i<=n;++i){ scr[i].all=c1*scr[i].x+c2*scr[i].y+(100-c1-c2)*scr[i].z; } sort(scr+1,scr+n+1,cmp); int scr1=-1,rck=-1; //for(int i=1;i<=n;++i)) printf("c1=%d,c2=%d,scr[%d]=%d\n",c1,c2,i,scr[i].all); for(int i=1;i<=n;++i){ if(scr1!=scr[i].all){ scr1=scr[i].all; rck=i; } if(scr[i].b==true){ if(rck<ans) ans=rck; break; } } } } printf("%d",ans); return 0; }
(中间有一些注释是我比赛时debug用的) (其实H1也能枚举过,不过枚举的精度应当是1/2907,因为似乎有个测试数据跟17或19有点关系(2907=9*17*19))
- 1
Information
- ID
- 160
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- (None)
- # Submissions
- 242
- Accepted
- 16
- Uploaded By