baizhiren

96

Mr.Az
thomas_wmy
AcWing2AK

# 暴力枚举 35ms

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int n;

int r1x, r1y, r2x, r2y;
const int N = 2010;
double d1[N], d2[N];
double d(double x1,  double y1, double x2, double y2){
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double ans = 1e18;
void dfs(int i, double r1, double r2){
if(r1 * r1 + r2 * r2 >= ans) return;
if(i > n){
ans = r1 * r1 + r2 * r2;
}
if(d1[i] <= r1 || d2[i] <= r2) dfs(i + 1, r1, r2);
else{
dfs(i + 1, d1[i], r2);
dfs(i + 1, r1, d2[i]);
}
}
int main(){
cin >> n;
cin >> r1x >> r1y >> r2x >> r2y;
for(int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y;
d1[i] = d(r1x, r1y, x, y);
d2[i] = d(r2x, r2y, x, y);
}
dfs(1, 0, 0);
cout << (long long)(ans + 0.5);
return 0;
}


baizhiren
1个月前

# 思路

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N, INF = 1e9 + 10;
typedef long long LL;
int h[N], e[M], ne[M], idx;
int s[N];
int n;
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool flag = true;
LL dfs(int u){
LL ans = 0;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
int cnt = 0;
int m = INF;
for(int k = h[j]; ~k; k = ne[k]){
cnt ++;
int son  = e[k];
int w = s[son] - s[u];
if(w < 0)  flag = false;
m = min(w, m);
ans += dfs(son) + w;
}
if(m != INF)
ans -= (cnt - 1) * m;
}
return ans;
}

int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i++){
int a;
cin >> a;
}
for(int i = 1; i <= n; i++){
cin >> s[i];
}

LL ans = dfs(1);
if(flag)
cout << ans + s[1];
else
cout << -1;

}


baizhiren
9个月前
#include<stdio.h>
#include<stdlib.h>
void swap(int& a,int& b ){
int tmp;
tmp=a;
a=b;
b=tmp;
}
void quick_sort(int q[],int l,int r){
if (l>=r) return;
int i=l-1,j=r+1,x=q[(l+r)/2];
while(i<j){
do i++; while(q[i]<x);
do j--; while(q[j]>x);
if (i<j) swap(q[i],q[j]);
else break;
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}

int q[100000+10];
int main(){
int n;
scanf("%d",&n);
for (int i=0;i<n;i++){
scanf("%d",&q[i]);
}
quick_sort(q,0,n-1);
for (int i=0;i<n;i++){
printf("%d ",q[i]);
}
system("pause");
return 0;
}