c++ 【基础】海岛寻宝

【基础】海岛寻宝

时间限制: 1.000 Sec 内存限制: 16 MB
题目描述
某个海岛上埋藏着多件宝物，每件宝物都有一个确切的位置，宝物的位置用一对数（x，y）来表示。其中 x表示该宝物离海洋中某个指定地点的水平距离，y表示该宝物离海洋中某个指定地点的垂直距离。已知宝物离海洋某个指定地点的直线距离L可以由如下公式计算：

海洋探险队的任务是：找出名称包含某种特征字符串的所有宝物，并按直线距离由近到远的顺序把它们的位置记录下来，以方便将来取出宝物。假若你是海洋探险队的一员，你能编程完成这一工作吗？

输入
共有n+2行。
第1行为要寻宝物的特征字符串；
第2行为岛上的宝物数n（ 0 < n <= 100 ）；
第3行至第n+2行为每件宝物的位置数据和宝物名称。
输出
按距离由近到远输出所找到宝物的位置，每件宝物的位置数据占一行。若找不到宝物，则全以“-1”输出（输出n个-1）。
样例
输入1 复制
ep
2
1.5 2.8 goden
2.4 5 word
输出1 复制
-1 -1
输入2 复制
ner
3
5 2.4 liner
2.5 8.3 suerp
1.5 2 winervis
输出2 复制
1.5 2
5 2.4

错误代码：

#include <bits/stdc++.h>
using namespace std;

struct ikun {
    double x;
    double y;
    string name;
};

bool compareDistance(const ikun& t1, const ikun& t2) {
    return sqrt(pow(t1.x, 2) + pow(t1.y, 2)) < sqrt(pow(t2.x, 2) + pow(t2.y, 2));
}

int main() {
    string feature;
    int n;
    cin >> feature >> n;

    vector<ikun> treasures(n);
    for (int i = 0; i < n; i++) {
        cin >> treasures[i].x >> treasures[i].y >> treasures[i].name;
    }

    vector<ikun> foundTreasures;
    for (const auto& treasure : treasures) {
        if (treasure.name.find(feature) != string::npos) {
            foundTreasures.push_back(treasure);
        }
    }

    if (foundTreasures.empty()) {
        cout << "-1 -1" << endl;
    } else {
        sort(foundTreasures.begin(), foundTreasures.end(), compareDistance);
        for (const auto& treasure : foundTreasures) {
            cout << treasure.x << " " << treasure.y << endl;
        }
    }

    return 0;
}

你稍等一会，代码马上给你，思路：字符串先判断，在算距离，最后排序输出
代码：

#include<bits/stdc++.h>
using namespace std; 
struct node{
    double x,y;
    double dis;
    bool flag=false;
    string name;
}a[10005];
bool cmp1(node t1,node t2)
{
    return t1.flag>t2.flag;
}
bool cmp2(node t1,node t2)
{
    return t1.dis<t2.dis;
}
int main()
{
    string str;
    int n;
    cin>>str>>n;
    for(int i=1;i<=n;i++) 
    {    
        cin>>a[i].x>>a[i].y>>a[i].name;
        a[i].dis=sqrt(pow(a[i].x,2)+pow(a[i].y,2));
    }
    int num=0;
    for(int i=1;i<=n;i++)
    {
        int b=a[i].name.find(str);
        if(b!=string::npos)
        {
            a[i].flag=true;
            num++;
        }
    }
    sort(a+1,a+n+1,cmp1);
    sort(a+1,a+num+1,cmp2);
    for(int i=1;i<=n;i++) 
    if(a[i].flag) cout<<a[i].x<<" "<<a[i].y<<endl; 
    else cout<<"-1 ";
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct Treasure {
  double x;
  double y;
  string name;
};

double distance(const Treasure& t) {
  return sqrt(pow(t.x, 2) + pow(t.y, 2));
}

int main() {
  string feature;
  int n;
  cin >> feature >> n;

  vector<Treasure> treasures{
    {1.1, 2.2, "金币"},
    {3.3, 4.4, "钻石"},
    {5.5, 6.6, "银币"}   
  };

  auto found = find_if(treasures.begin(), treasures.end(),
    [&feature](const auto& t) {
      return t.name.find(feature) != string::npos;
    });

  if (found == treasures.end()) {
    cout << "-1 -1";
  } else {
    sort(found, treasures.end(),
      [](const auto& t1, const auto& t2) {
        return distance(t1) < distance(t2);  
      });
    
    for (const auto& t : found) {
      cout << t.x << " " << t.y << "\n"; 
    }
  }
}

结果
1.

2.

代码

#include <bits/stdc++.h>
using namespace std;

struct Ikun {
  double x;
  double y;
  string name;
};

bool CompareDistance(const Ikun& t1, const Ikun& t2) {
  return sqrt(pow(t1.x, 2) + pow(t1.y, 2)) < sqrt(pow(t2.x, 2) + pow(t2.y, 2));
}

int main() {

  string feature;
  int numTreasures;
  cin >> feature >> numTreasures;

  vector<Ikun> treasures(numTreasures);
  for (int i = 0; i < numTreasures; i++) {
    cin >> treasures[i].x >> treasures[i].y >> treasures[i].name;
  }

  vector<Ikun> foundTreasures;
  for (const auto& treasure : treasures) {
    if (feature.empty() || treasure.name.find(feature) != string::npos) {
      foundTreasures.push_back(treasure);
    }
  }

  if (foundTreasures.empty()) {
    for (int i = 0; i < numTreasures; i++) {
      cout << "-1 -1" << endl;
    }
  } else {
    sort(foundTreasures.begin(), foundTreasures.end(), CompareDistance);
    for (const auto& treasure : foundTreasures) {
      cout << treasure.x << " " << treasure.y << endl; 
    }
  }

  return 0;

}

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7427549
• 除此之外, 这篇博客: Educational Codeforces Round 102 (Rated for Div. 2)中的 思路：首先考虑在没有删除的情况下，一系列操作过程中，能变成多少不同的值。x初始为0，随着+±-的变化，会来回反复横跳，那么两个关键点就是最大值和最小值，这说明从最大值到最小值之间的数字，都是在操作过程中出现。所以只需要考虑一个区间内的操作产生的最大最小值。但是题目要删掉，中间一段，剩下两段，也就是要把两段合并起来。画个图其实更好理解。红色的是所有的操作，绿色的是要删除的操作，第二个曲线就是合并之后的x值变化曲线。由图可知。后面那部分合并过来之后，起点就是前面那部分的终点！这就是关键点。然后前面那部分的区间的最大最小值和当前值都很好维护。难的是后面那部分怎么维护。后面那部分，从后往前维护，每到一个点，都认为这个点是零点，然后计算最大值最小值。因为是反着来，可以发现操作曲线是一个与 原操作 关于x轴对称的曲线，所以最大值就是最小值，最小值就是最大值。然后最小值就是 当前点到最小值的距离，最大值就是 当前点到最大值的距离。之所以算距离，是因为，永远认为当前点是0点。所以 距离 才是真正的最大最小值。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

•