2023牛客寒假算法基础集训营3 B-勉强拼凑的记忆

2023 年 01 月 21 日

244 次浏览

877字数

![](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/2419413528.png)题目大意，一共有n块积木，每块长度是n/2向上取整，问最大拼成正方形的最大边长。

解法：l是n/2向上取整，先用l块木块拼成一个正方形，每增加一层需要三个木块，然后看n-l以后还能剩多少块，然后再整除3，看看能凑出几个就是答案了,经过严密的猜测，只有2是无解的，经过验证，如果多出来木块的话，可以缩短已经放好的木块长度，所以总是放的下的。这里我用了ceil(n * 1.0 / 2)出了问题，所以以后的木块都不用ceil函数，向上取整是(n + (n - 1) / 2,四舍五入是(n + 0.5)

```C++
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

void solve(){
    ll n;
    cin >> n;
    if(n == 2){
        cout << "-1\n";
    }
    else{
        ll l = (n + 1) / 2;
        ll ans = l + (n - l) / 3;
        cout << ans << endl;
    }
}
int main(){
    IOS;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

```

最后修改：2023 年 02 月 02 日