- gf25051 的博客
记录
-
gf25051
LV 6
@
2026-4-30 13:54:13
格蕾丝的逃离题解
方法一
暴力搜索
我们分别枚举公主和革命军的速度
60分版本
#include <bits/stdc++.h>
using namespace std;
int d,l,n,a,b,cnt;
int v[500005];
int main() {
cin>>d>>l>>n;
for(int i=1; i<=n; i++) {
cin>>v[i];
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
int g=v[i];
int z=v[j];
if(g<=z){
continue;
}
if(d*z<l*(g-z)){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
但只要我们把int改为long long，就能拿80分
80分版本
#include <bits/stdc++.h>
using namespace std;
long long d,l,n,a,b,cnt;
int v[500005];
int main() {
cin>>d>>l>>n;
for(int i=1; i<=n; i++) {
cin>>v[i];
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
int g=v[i];
int z=v[j];
if(g<=z){
continue;
}
if(d*z<l*(g-z)){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
再加一个sort排序优化一下
90分版本
#include <bits/stdc++.h>
using namespace std;
long long d,l,n,a,b,cnt;
int v[200005];
bool cmp(int x,int y) {
return x<y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>d>>l>>n;
for(int i=1; i<=n; i++) {
cin>>v[i];
}
sort(v+1,v+1+n,cmp);
for(int i=1; i<=n; i++) {
for(int j=1; j<i; j++) {
int g=v[i];
int z=v[j];
if(d*z<l*(g-z)) {
cnt++;
}
}
}
cout<<cnt;
return 0;
}
这就是暴力搜索的极限了
方法二
二分查找
查找第一个>=革命军追上公主的速度，剩余部分累加即可
100分版本
#include <bits/stdc++.h>
using namespace std;
long long d,l,n,a,b,cnt;
int v[200005];
bool cmp(int x,int y) {
return x<y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>d>>l>>n;
for(int i=0; i<n; i++) {
cin>>v[i];
}
sort(v,v+n,cmp);
for(int i=0; i<n; i++) {
int g=v[i];
int need=(g*(d+l))/l+1;
if(need<g+1){
need=g+1;
}
int erfen=lower_bound(v,v+n,need)-v;
cnt+=n-erfen;
}
cout<<cnt;
return 0;
}