1433吃奶酪 贪心 答案出错
  • 板块题目总版
  • 楼主MayBro
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/9/18 21:04
  • 上次更新2023/11/2 19:12:15
查看原帖
1433吃奶酪 贪心 答案出错
596696
MayBro楼主2023/9/18 21:04

突然灵光一现能不能用贪心,每次去吃距离自己最近的奶酪,吃完后输出,最后只能50分,有一半wrong answer了,虽然知道这道题应该用DP,但想不通为什么不能贪心(内心隐隐约约感觉有点问题),求大神指点QWQ

https://www.luogu.com.cn/record/125128950```cpp

#include <iostream>
#include "math.h"
using namespace std;
int n;
struct node{
    double x=0,y=0;
//    node(double xx=0,double yy=0){
//        x=xx,y=yy;
//    }
}arr[20];
int vis[20];
double ans;
double dis(node a,node b){
    return sqrt(pow((a.x-b.x),2)+pow(a.y-b.y,2));
}
void search(node a,int deep){
    if(deep>n){
        printf("%.2f",ans);
        return;
    }
    int mini;
    double mins=0xfffffffffffff;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            double tmp=dis(a,arr[i]);
            if(tmp<mins){
                mini=i;
                mins=tmp;
            }
        }
    }
    vis[mini]=1;
    ans+=mins;
    search(arr[mini],deep+1);
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr[i].x>>arr[i].y;
    search(arr[0],1);
    return 0;
}
2023/9/18 21:04
加载中...