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; }