예제 7-7 UVA 1354 Mobile Computing(검색+두 갈래 트리(클래스 하프만 트리)

생각:
생각해 보면 결점 하나에 아들이 둘 있거나 없거나 알 수 있다.
그러면 이것은 하프만 나무와 비슷하기 때문에 우리는 모든 하프만 나무를 일일이 들 수 있다.
그리고 뿌리 결점부터 두 갈래 나무를 훑어보는 동시에 왼쪽과 오른쪽의 최대치를 일일이 열거한다.
그리고 R-L이 바로 이 두 갈래 나무의 너비이다.
답을 업데이트하면 됩니다!
작은 구덩이가 하나 있는데 눈치채지 못했다.
단지 하나의 분동이 있을 때, 답은 0이 아니라 -1이어야 한다.
생각해 보니 여전히 현실적이다.
단지 하나의 분동만 있으면 바로 밧줄로 매달면 된다. 제목에서 분동의 넓이를 고려하지 않는다고 하면 0이 아니냐!!
코드 참조:
#include 
#include 
#include 
#include 
#include 
#include 
#define Siz(x) (int)x.size()
using namespace std;
const double eps = 1e-10;
int dcmp(double a,double b){
    if (fabs(a-b) < eps) return 0;
    if (a < b) return -1;
    return 1;
}
struct Node{
    int v;
    int ban;
    Node* left;
    Node* right;
    Node(int v = 0,int ban = 0):v(v),ban(ban){
        left = right = NULL;
    }
};
int T, n;
double r;
double L,R,ans;
vectorv;
void dfs2(Node* cur,double dis){
    if (cur->left == NULL || cur->right == NULL) return;
    int lv = cur->left->v;
    int rv = cur->right->v;
    double k = rv*1.0/lv;
    double a = k/(1+k);
    double b = 1.0/(1+k);
    double nl = dis - a;
    double nr = dis + b;
    if (dcmp(L,nl) == 1) L = nl;
    if (dcmp(R,nr) == -1) R = nr;
    dfs2(cur->left,nl);
    dfs2(cur->right,nr);
}

void dfs(int siz){
//    printf("%d
",siz); if(siz > 1){ for (int i = 0; i < Siz(v); ++i){ for (int j = 0; j < i; ++j){ if (i != j){ // printf("%d %d
",i,j); Node* ii = v[i]; Node* jj = v[j]; v.erase(v.begin()+i); v.erase(v.begin()+j); // puts("hahahaha"); Node* kk = new Node(ii->v + jj->v); kk->ban = 1; kk->left = new Node(); kk->right = new Node(); kk->left = ii; kk->right = jj; v.push_back(kk); dfs(siz-1); v.pop_back(); kk = new Node(ii->v + jj->v); kk->ban = 1; kk->left = new Node(); kk->right = new Node(); kk->left = jj; kk->right = ii; v.push_back(kk); dfs(siz-1); v.pop_back(); if (j >= Siz(v))v.push_back(jj); else v.insert(v.begin()+j,jj); if (i >= Siz(v))v.push_back(ii); else v.insert(v.begin()+i,ii); } } } } else { // puts("ahahah"); Node* root = new Node(); root = *(v.begin()); // printf("%d
",root->v); L = 1e18; R = -1e18; dfs2(root,0); double nnr = R-L; if (dcmp(nnr,r) != 1){ // ans = max(ans,nnr); if (dcmp(ans,nnr) == -1) ans = nnr; } } } int main(){ scanf("%d",&T); while(T--){ v.clear(); ans = -1e18; scanf("%lf%d",&r,&n); for (int i = 0; i < n; ++i) { int vv; scanf("%d",&vv); v.push_back(new Node(vv,0)); } dfs((int)v.size()); if(n == 1) puts("0"); /// , 0, -1. else if (ans == -1e18) puts("-1"); else printf("%.16f
",ans); } return 0; }

좋은 웹페이지 즐겨찾기