struct Edge

人丑就要學技術

BZOJ 2048 題解

2048: [2009國家集訓隊]書堆

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 1076 Solved: 499
[Submit][Status][Discuss]

Description

Input

第一行正整數 N M

Output

一行（有換行符），L，表示水平延伸最遠的整數距離 (不大于答案的最大整數)

Sample Input

樣例
#1
Input: 1 100
Output: 49

#2
Input: 2 100
Output: 74

Sample Output

N <= 10^18
數據保證答案 < 10^6

————————————————————————————

物理題：

從最上一本書考慮，當重心落在下一本書的邊緣，由于力矩平衡，恰好不落下。

兩本書整體根據力矩平衡，重心左移m/4距離。

兩本書整體根據力矩平衡，重心左移m/6距離。

兩本書整體質心根據力矩平衡，重心左移m/8距離。

于是現在題目求( m/2 + m/4 + m/6 + m/8 + ... + m/n ) ，不難發現，這道題與調和級數有關。

根據上述公式，代碼如下：

/**************************************************************
    Problem: 2048
    User: shadowland
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1300 kb
****************************************************************/
 
#include "bits/stdc++.h"
 
using namespace std ;
typedef long long QAQ ;
typedef double db ;
const db Euler_const = 0.5772156649015328606065120900824024310421593359 ; 
const db eps = 1e-10 ;
 
int main ( ) {
        db tmp = 0.0000 , N , M ;
        cin >> N >> M ; 
        if ( N <= 1e4 ) for ( int i=1 ; i<=N ; ++i ) tmp += ( 1.000 / ( db ) i ) ;
        else tmp = log ( N + 1.000 ) + Euler_const ; 
        tmp *= ( M * 0.500 ) ;
        cout << ( QAQ ) ceil ( tmp - 1 ) << endl ;
        return 0 ;  
}

View Code

2016-10-29 00:56:53

posted @ 2016-10-29 00:57 SHHHS 閱讀(523) 評論(0) 收藏舉報

刷新頁面返回頂部