882.细分图中的可到达节点

链接：882.细分图中的可到达节点
难度：Hard
标签：图、最短路、堆（优先队列）
简介：返回中枢整数 x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。

题解 1 - cpp

• 编辑时间：2022-11-27
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：遍历对每个值尝试。

# define X first
# define Y second
# define lb(x) ((x) & (-x))
# define mem(a,b) memset(a,b,sizeof(a))
# define debug freopen("r.txt","r",stdin)
# define pi pair<int,int>
using namespace std;
typedef long long ll;
class Solution {
public:
    int pivotInteger(int n) {
        int sum = (1 + n) * n / 2;
        int prev_sum = 0;
        for (int i = 1; i <=n ; i++) {
            int next_sum = sum - prev_sum;
            prev_sum += i;
            if (prev_sum == next_sum) return i;
        }
        return -1;
    }
};