寻找门牌

题目

小f乘坐南十字船队的船偷渡到了稻妻，在这里，他遇上的第一个麻烦是雷神对外国人的封锁。如果他要觐见雷神，就必须要逃离被封锁起来的离岛。在托马的帮助下，他遇到了想要偷偷给男友送信的佟千里小姐。小f在她的帮助下离开了离岛，秘密给她的男友送信。

小f发现了一个有趣的现象：佟千里的男友居住在一个胡同里，胡同的门牌号从1开始编号，胡同里各家门牌号的和减去三倍他家的门牌号码的结果刚好为 n。小f想考考你，佟千里的男友所在的胡同中有多少户，而他家的门牌号又是多少呢？

输入：一个整数 n。
输出：共两个数，表示胡同总户数以及他家的门牌号。如果存在多个解，只输出胡同中总户数最少的情况；如果在规定范围内不存在解，请输出 Impossible!。
数据范围：n ≤ 3000，数据在 [1, 10000] 内有解。

样例：

100

16 12

思路

枚举胡同户数 m，由 sum = m(m+1)/2 反推门牌号 k = (sum−n)/3， 检查 k 是否为正整数且在 [1, m] 内，第一个满足条件的即为答案； 否则输出 Impossible!。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,sum,k;
    cin>>n;
    for(int c=0;c<10000;c++){
        sum=c*(c+1)/2;
        if((sum-n)%3==0){
            k=(sum-n)/3;
            if(k>=1&&k<=c){
                cout<<c<<" "<<k<<endl;
                return 0;
            }
        }
    }
    cout<<"Impossible!"<<endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(M)，M = 10000，最多枚举一万次。
• 空间复杂度：O(1)。

← 返回菜鸟的coding