首页 > 试题广场 >

游游的整数操作

[编程题]游游的整数操作

热度指数：884 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游拿到了一个数组，她有两种操作；
1. 输入1 x，代表所有数加x。
2. 输入2 x，代表所有数减x，同时将所有的负数变成0。即对于每个 $a_i$ ，把 $a_i$ 变成 $max(a_i-x,0)$ 。

游游在操作结束后，希望你能告诉她所有数之和，答案对 $10^9+7$ 取模。

输入描述:

第一行输入两个正整数和，代表数组长度以及操作次数。
第二行输入个正整数。代表初始的数组。
接下来的行，每行输入两个正整数和。其中op代表操作类型。

输出描述:

操作结束后所有数之和对取模的值。

示例1

输入

输出

说明

第一次操作后，数组变成 [0,0,1,2,3]
第二次操作后，数组变成 [1,1,2,3,4]

算法知识视频讲解

Handa_Rei

排序+二分查找。

因为排序后，一旦某个数字在某次操作后小于等于0，那么他之前的数字都和他一样会变成0。因此设置两个变量acc0和acc,分别代表那些曾经变为0的数字要加的值和从来没有变为过0的数字要加上的值。

from bisect import bisect_right

n, k = map(int, input().split())
a = list(map(int, input().split()))
tmpa = a.copy()
a.sort()
acc = 0
accfor0 = 0
for _ in range(k):
    op, x = map(int, input().split())
    if op == 1:
        acc += x
        accfor0 += x
    else:
        acc -= x
        accfor0 = max(0, accfor0 - x)
        if acc < 0:
            idx = bisect_right(tmpa, -acc)
            tmpa = tmpa[idx:]

MOD = 10 ** 9 + 7
num1 = len(tmpa)
num0 = n - num1
ans = accfor0 * num0
ans += sum(n + acc for n in tmpa)
print(ans % MOD)

发表于 2023-09-22 00:03:39 回复(0)

牛客337566631号

import java.math.BigInteger;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
private final static int mod = (int) Math.pow(10, 9) + 7;;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
long count = 0;
int n = in.nextInt();
int k = in.nextInt();
int index = 0;
long num[] = new long[n];
int len = 0;

int opx[] = new int[k];

// 初始化数据记录操作数组转换为正负操作

while (in.hasNextInt()) {
if (index < n) {
num[index++] = in.nextInt();
} else {
int b = in.nextInt();
if (b == 1) {
opx[len] = in.nextInt();
} else {
opx[len] = -in.nextInt();
}
len++;
}
}
long add = 0;
long sub = 0;

long current = 0;

//统一对操作数组进行替换对于一个数如果前面的操作大于0 则可以把前面那一步操作和后面的操作加起来，按这个推，最后一定只剩下一次减和一次加

for (int i = 0; i < opx.length; i++) {
current = (current + opx[i]);
if (opx[i] < -current) {
if (current < 0) {
sub = (sub + current);
current = 0;
}
}
add = current;

}

//遍历数组如果这个数比总的减去的值还大那么不为0 所以加起来，如果小于那么肯定为0直接等于最后操作的正数

for (int i = 0; i < n; i++) {
if (num[i] > -sub) {
num[i] = num[i]+add+sub ;
} else {
num[i] = add;
}
count = (count + num[i]) % mod;
}
System.out.println(count);
}

}

发表于 2023-08-30 14:37:31 回复(0)

梦蝶_

差分数组+排序，记录变 0 的数组下标，排序 O(nlogn)，操作 O(n + k)，最后统计 O(n)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    const int MOD = 1000000007;
    int n, k, op, x;
    cin >> n >> k;
    vector<ll> a(n);
    vector<ll> diff(n); // 差分数组
    ll p = n, val; // 记录被变成 0 的位置，及其对应的值
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<ll>());
    val = a[n - 1];
    diff[0] = a[0];
    for (int i = 1; i < n; ++i) diff[i] = a[i] - a[i - 1];
    for (int i = 0; i < k; ++i) {
        cin >> op >> x;
        // op 1
        if (op == 1) {
            diff[0] += x;
            val += x;
        }
        // op 2
        else if (op == 2) {
            diff[0] -= x;
            val -= x;
            while (p > 0 && val < 0) {
                val -= diff[--p];
                if (val > 0) val = 0;
            }
            if (p == 0 && val < 0) diff[0] = 0, val = 0;
        }
    }
    ll ans = diff[0], cnt = diff[0];
    if (p == 0) ans = (val % MOD)* n;
    else {
        for (int i = 1; i < p; ++i) {
            cnt += diff[i];
            ans += cnt;
            ans %= MOD;
        }
        ans += (n - p) * val;
    }
    ans %= MOD;
    printf("%lld", ans);
    return 0;
}

编辑于 2023-09-21 15:59:49 回复(3)

昵称被自己占了

nk = list(map(int, input().split()))
# 获取数组
my_list = list(map(int, input().split()))
# 经过我缜密的分析,数据只有两种情况,要么比基准线高,要么比基准线低,
# 基准线及对应值
ji = 1
number = 1
# 计算基准线对应值
for _ in range(nk[1]):
    op_x = list(map(int, input().split()))
    if op_x[0] == 1:
        number += op_x[1]
    else:
        number -= op_x[1]
        if number < 0:
            # 上调基准值
            ji -= number
            number = 0
# 计算和
my_sum = number * len(my_list)
my_sum += sum(item - ji for item in my_list if item > ji)

print(my_sum % (10**9 + 7))

发表于 2023-10-02 23:17:24 回复(0)

善良的灯泡

我是这样写的，好像要简洁一点，过了

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
const lines = []
rl.on('line', function (line) {
    lines.push(line)
    const [n, k] = lines[0].split(' ').map(Number)
    if (lines.length === k + 2) {
        const arr = lines[1].split(' ').map(Number)
        let add = 0, sub = 0
        for (let i = 2; i < lines.length; i++) {
            const [op, x] = lines[i].split(' ').map(Number)
            if (op === 1) add += x
            else {
                if (x > add) {
                    sub += x - add
                    add = 0
                }
                else add -= x
            }
        }
        let sum = 0
        for (let i = 0; i < arr.length; i++) {
            arr[i] = Math.max(arr[i] - sub,0)
            sum = (sum + arr[i] + add) % 1000000007
        }
        console.log(sum)
    }
});

发表于 2023-07-24 13:49:41 回复(0)

小师弟想要offer

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

const int MOD = 1e9 + 7;
vector<long long> f , ops;
int n , k ;

bool check(int c){
    long long sum = f[c] ;
    for(long long i : ops){
        sum += i;
        if (sum < 0){
            return true;
        }
    }
    return false;
}
int main() {
    long long res = 0, opsum = 0;
    
    cin>> n >> k ;
    for(int i = 0 ; i < n ; i ++){
        int tp;
        cin>>  tp ;
        f.push_back(tp);
    }

    sort(f.begin(),f.end());

    int preop = 0;
    for(int i = 0 ; i < k ; i ++){
        int op, x;
        cin>> op >> x ;
        if(op == 2){
            x = -x;
        }
        ops.push_back(x);
        opsum = (x + opsum)%MOD;
    }
    // 找到 在操作过程中，所有不会变为负数的部分，另一部分则代表，在操作过程中会产生负数
    long long left = 0, right = n-1;
    while(left < right){
        int mid = (left + right) /2;
        if(check(mid)){
            left = mid + 1;
        }else {
            right = mid -1;
        }
    }
    // 此时 找到left，代表left右边所有的数，在操作过程中不会产生小于0的情况
    for(int i = left + 1; i < n ; i ++){
        res = (f[i] + res)%MOD ;
    }
    res = (res%MOD + (opsum * (n - left - 1) )%MOD)%MOD ;

    // 此时左边的数，最终都会相等
    // 这里要用 128位 不然会爆炸
    in left_sum = f[left] ;
    for(long long o : ops){
        left_sum  = (left_sum  + o) ;
        left_sum = max( (in)0 , left_sum);
    }
    res = res%MOD + ((left + 1) * left_sum%MOD)%MOD;

    cout<<res%MOD<<endl;
}

发表于 2023-07-19 23:52:04 回复(0)

Java

你爸边哭边

import java.io.*;
import java.util.*;

public class Main {
    static long[] nums,op;
    static boolean check(int p){
        long ans=nums[p];
        for(int i=0;i<op.length;i++){
            ans+=op[i];
            if(ans<=0)
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n=in.nextInt(),k=in.nextInt(),mod=(int)1e9+7;
        long res=0,sum=0;
        nums=new long[n];
        op=new long[k];
        for(int i=0;i<n;i++){
            nums[i]=in.nextInt();
        }
        for(int i=0;i<k;i++){
            int c=in.nextInt();
            if(c==2)
                c=-1;
            else
                c=1;
            op[i]=c*in.nextInt();
            sum+=op[i];
            sum%=mod;
        }
        Arrays.sort(nums);
        int l=0,r=n-1,mid=0,left=n;
        while(l<=r){
            mid=l+(r-l)/2;
            if(check(mid)){
                left=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        for(int i=left;i<n;i++){
            res+=nums[i];
            res%=mod;
        }
        res+=(long)(n-left)*sum%mod;
        if(left>=1){
            long ans=nums[left-1];
            for(int i=0;i<op.length;i++){
                ans+=op[i];
                if(ans<0)
                    ans=0;
            }
            res+=ans%mod*left;
        }
        res%=mod;
        out.println(res%mod);
        out.flush();
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }

}

发表于 2023-07-11 16:15:21 回复(2)

提交观点

问题信息

来自：2023年携程秋招技术...

难度：

7条回答 25收藏 2261浏览

游游的整数操作

输入描述:

输出描述:

输入

输出

说明

排序+二分查找。

问题信息

热门推荐

相关试题