小红书Red Star提前批算法笔试

小红的数组构造

题目描述：

小红的数组构造小红希望你构造一个数组满足以下条件：1. 数组共有n个元素，且所有元素两两不相等。2. 所有元素的最大公约数等于k。3. 所有元素之和尽可能小。请你输出数组元素之和的最小值。

输入描述

两个正整数n和k

1≤ n,k ≤ 10^5

输出描述

一个正整数，代表数组元素之和的最小值。

样例输入

3 1

样例输出

6

示例 2

输入

2 2

输出

6

#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    cout << ((1+n)*n/2) * k << endl;
    return 0;
}

精华帖子

题目描述：

小红书的推荐帖子列表为[0,n]，其中所有的帖子初始状态为“普通”，现在运营同学把其中的一些帖子区间标记为了“精华”。

输入描述

第一行输入两个正整数n,m,k，代表初始帖子列表长度，精华区间的数量，以及运营同学准备截取的长度。

接下来的m行，每行输入两个正整数li,ri，代表第i个区间。

1 ≤ k ≤ n ≤ 1000000000

1 ≤ m ≤ 100000

0 ≤ li < ri ≤ n

保证任意两个区间是不重叠的。

输出描述

一个正整数，代表最多的精华帖子数量。

样例输入

5 2 3

1 2

3 5

样例输出

2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;  

    vector<vector<int>> itv(m, vector<int>(2));  

    for (int i = 0; i < m; i++) {
        cin >> itv[i][0] >> itv[i][1];  
    }

    sort(itv.begin(), itv.end());
    vector<int> pres(m+1, 0);

    for (int i = 1; i <= m; i++) pres[i] = pres[i-1] + (itv[i-1][1] - itv[i - 1][0]);  // 计算前缀和

    int res = 0;  // 初始化结果为0

    for (int i = 0 ; i < m ; i++) {

        int l = i, r = m ;
        // 使用二分查找找到满足条件的区间
        while (l < r) {
            int mid = (l + r) / 2;
            if (itv[mid][1] >= itv[i][0] + k) r = mid;
            else l = mid + 1;
        }