C题求助

C题WA了28发,不知道哪里错了,哭了^_^
我的思路是贪心,枚举所有可以选择的点,然后每次都选择可以向交最多现有的园的点, 这个哪里错了,过了90%case ...
求助大佬
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e5+7;
struct cir{
    ll x,y,r;
}a[30];
int tag[30];
int can(ll x1,ll y1,ll R,ll x2, ll y2, ll r){
    if(((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))<=(r+R)*(r+R)) return 1;
    return 0;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,ku,r,R;
    cin>>n>>ku>>R;
    for(int i=0;i<n;i++){
        tag[i]=0;
        cin>>a[i].x>>a[i].y>>a[i].r;
    }
    if(n<=ku){
        cout<<n;
        return 0;
    }
    int ans = 0, range=3500;
    for(int i=0;i<ku;i++){
        ll xx=0,yy=0, now=0;
        for(ll tx=-range;tx<=range;tx++){
            for(ll ty=-range;ty<=range;ty++){
                ll tn = 0;
                for(int j=0;j<n;j++){
                    if(tag[j]) continue;
                    if(can(tx,ty,R,a[j].x,a[j].y,a[j].r)) tn++;
                }
                if(tn>=now) xx = tx, yy=ty ,now=tn;
            }
        }
        if(now==0) break;
        for(int j=0;j<n;j++){
            if(tag[j]) continue;
            if(can(xx,yy,R,a[j].x,a[j].y,a[j].r)) tag[j]=1, ans++;
        }
    }
    cout<<ans;
}



全部评论
我觉得贪心不行,说下我的想法:比如一块包含很多点的区域,可以用2个圆覆盖,但是,你选了中间点最多(最密集)的地方,就要用3个圆覆盖
2 回复 分享
发布于 2021-02-05 18:28
提供一组反例/* 10 2 3 0 0 1 1 0 1 1 1 1 1 -1 1 -1 0 1 -1 1 1 -1 -1 1 2 0 1 5 0 1 -5 0 1 */
点赞 回复 分享
发布于 2021-02-05 18:42

相关推荐

KalznAsawind:标准的八股问烂简历,面试官碰到这种简历一般都会开始轰炸八股了。其实我一直觉得项目、实习的作用是将面试官困在你的语境中,在你的语境中跟他解释项目背景和细节,跟他battle,减少他轰炸你八股的时间,这样压力会小很多。但是你的项目是一眼无落地、无背景的包装项目,所以对方也不会去在意你的项目背景,只会针对你的项目涉及的技术栈开始轰炸八股,会增大你的压力,而你面试过不过全看你八股背的熟不熟。
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务