序列维护

思路

• 暴力解法
  暴力解法很容易想到，直接按题目说的来做就可以了
• 优化
  这个数据量，显然需要用O(nlogn)或者O(n)算法，则会想到排序，如果从大到小排，那么每次查询一个数字x，使得大于等于x的数字都会-1，那么数列还是有序的。也就是数列始终都是有序的，这样就可以进行剪枝了，遍历到小于x的直接break跳出循环即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int a[N], hs[N];
int n, q, x;

int main() {
    scanf("%d%d", &n, &q);
    int x;
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1, greater<int>());

    while (q -- ) {
        scanf("%d", &x);
        int ret = 0;
        for (int i = 1; i <= n; ++ i) {
            if (a[i] >= x) {
                a[i] -= 1;
                ret ++ ;
            } else {
                break;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] arr = new int[n];
        //将数字录入数组
        for (int i = 0; i < n; i++) {
            int num = scanner.nextInt();
            arr[i] = num;
        }
        //先将数组排序
        Arrays.sort(arr);
        //查询次数
        for (int i = 0; i < q; i++) {
            //需要查询的数字
            int x = scanner.nextInt();
            System.out.println(demo4(arr, x));
        }
    }

    public static int demo4(int[] arr, int x) {
        int count = 0;
        //从大往小比较，碰到小于x的及时终止循环，能优化时间
        for (int i = arr.length-1; i >= 0; i--) {
            if (arr[i] >= x) {
                arr[i]--;
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}

n = list(map(int, input().split(' ')))
len = n[0]
N = n[1]
data = list(map(int, input().split(' ')))
while N:
    N = N-1
    num = 0
    val = int(input())
    for i in range(len):
        if(data[i] >= val):
            data[i] = data[i] - 1
            num = num+1
    print(num)

c = input('数字个数和操作次数：')
d = c.split(' ')
n,q = int(d[0]),int(d[1])


a = input('请输入初始数：')
b = a.split(' ', n)
list1 = []
for i in b:
    list1.append(int(i))


list2 = []
while q:
    x = int(input('指定数字：'))
    list2.append(x)
    q -= 1
    


for k in list2:
    list3 = []
    count = 0
    for j in list1:
        if j >= k:
            list3.append(j-1)
            count += 1
        else:
            list3.append(j)
    list1 = list3.copy()
    print('有' + str(count) + '个数字被减一。')

import sys
b = []#b存储第三行及之后的数据
n,p = map(int,sys.stdin.readline().strip().split())
a = list(map(int,sys.stdin.readline().strip().split())) #a存储第二行数据
for i in range(p):
    b.append(int(sys.stdin.readline().strip()))

for i in range(p):
    k = 0
    for j in range(n):
        if a[j] >= b[i]:
            a[j] -= 1
            k += 1
    print(k)

本地跑通，不知道为什么平台上不行

# 好笨的方法，别笑话我，加油

n = int(input("n = "))
q = int(input("q = "))
list1 = [i for i in range(1,n+1)]
for i in range(q):
    x = int(input("第" + str(i+1) + "次输入："))
    num = 0
    list2 = []
    for c in list1:
        if c >= x:
            list2.append(c-1)
            num = num + 1
        else:
            list2.append(c)
    print("本次操作中有{}个数被减一！".format(num))
    list1 = list2.copy()

#include <bits/stdc++.h>

using namespace std;

class segtree{
public:
  int n;
  int* data;
  int* tree;
  int* lazy;

  segtree(int* arr, int _n) : n(_n) {
    data = new int[_n];
    tree = new int[_n * 4];
    lazy = new int[_n * 4];
    fill_n(tree, _n * 4, 0);
    fill_n(lazy, _n * 4, 0);
    for (int i = 0; i < _n; i++) {
      data[i] = arr[i];
    }
    build(0, 0, n - 1);
  }

  ~segtree() {
    delete []data;
    delete []tree;
    delete []lazy;
  }

  void push(int tId) {
    tree[tId] = tree[tId * 2 + 1] + tree[tId * 2 + 2];
  }

  void pull(int tId, int l, int r) {
    int mid = (l + r) / 2;
    tree[tId * 2 + 1] += (mid - l + 1) * lazy[tId];
    tree[tId * 2 + 2] += (r - mid) * lazy[tId];
    lazy[tId * 2 + 1] += lazy[tId];
    lazy[tId * 2 + 2] += lazy[tId];
    lazy[tId] = 0;
  }

  void build(int tId, int l, int r) {
    if (l == r) {
      tree[tId] = data[l];
      return;
    }
    int mid = (l + r) / 2;
    build(tId * 2 + 1, l, mid);
    build(tId * 2 + 2, mid + 1, r);
    push(tId);
  }

  int get(int tId, int l, int r, int x) {
    if (l == r && l == x) {
      return tree[tId];
    }
    if (lazy[tId]) {
      pull(tId, l, r);
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
      return get(tId * 2 + 1, l, mid, x);
    } else {
      return get(tId * 2 + 2, mid + 1, r, x);
    }
  }

  void modify(int tId, int l, int r, int ml, int mr, int v) {
    if (ml <= l && r <= mr) {
      tree[tId] += (r - l + 1) * v;
      lazy[tId] += v;
      return;
    }
    if (lazy[tId] != 0) {
      pull(tId, l, r);
    }
    int mid = (l + r) >> 1;
    if (mr <= mid) {
      modify((tId * 2) + 1, l, mid, ml, mr, v);
    } else if (ml > mid) {
      modify((tId * 2) + 2, mid + 1, r, ml, mr, v);
    } else {
      modify((tId * 2) + 1, l, mid, ml, mid, v);
      modify((tId * 2) + 2, mid + 1, r, mid + 1, mr, v);
    }
    push(tId);
  }
};

int arr[234567];

int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
  sort(arr, arr + n);
  segtree st(arr, n);
  while (q--) {
    int x;
    int l = 0, r = n - 1;
    scanf("%d", &x);
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (st.get(0, 0, n - 1, mid) < x) l = mid + 1;
      else r = mid - 1;
    }
    if (l >= n) {
      cout << "0" << "\n";
    } else {
      cout << n - 1 - l + 1 << "\n";
      st.modify(0, 0, n - 1, l, n - 1, -1);
    }
  }
  return 0;
}

随机生成几组数试了一下
import random import numpy as np
n=random.randint(1,20)
x=np.random.randint(1,10,random.randint(1,10))
s=np.random.randint(1,20,n) for i in x: print(len(s[s>=i]))
     s=np.where(s>=i,s-1,s)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
arr.sort()
flag=0
for i in range(q):
    x=int(input())
    if x in arr:
        t=arr.index(x)
        arr[t:n]=[m-1 for m in arr[t:n]]
        print(n-t)
    else:
        for j in range(n):
            if arr[j]>=x:
                arr[j:n]=[m-1 for m in arr[j:n]]
                flag=1
                print(n-j)
                break
        
        if flag==0:
            print(0)

nq = input().split(" ")
n = int(nq[0])
q = int(nq[1])
 
def juge(x,datalist):
    rst = 0
    for i in range(len(datalist)):
        if datalist[i] >= x:
            rst += 1
            datalist[i] = datalist[i]-1
    return rst,datalist
 
result = []
sn = list(map(int,input().split(" ")))
for i in range(q):
    x = int(input().split(" ")[0])
    rst,sn = juge(x,sn)
    result.append(rst)
 
for j in result:
    print(j)

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static int search(int[] array,int value) {
		int left=0;
		int right=array.length-1;
		int mid=0;
		while(left<=right) {
			mid=(left+right)>>1;
			if(value<=array[mid])
				right=mid-1;
			else
				left=mid+1;
		}
		return left<array.length?left:array.length;
	}
	public static void main(String[] args){
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int q=scanner.nextInt();
		int[] a=new int[n];
		for(int i=0;i<n;i++) 
			a[i]=scanner.nextInt();
		Arrays.sort(a);
		for(int i=0;i<q;i++) {
			int x=scanner.nextInt();
			int ind=search(a, x);
			System.out.println(n-ind);
			for(int j=ind;j<n;j++)
				a[j]--;
		}
	}
}

while(line1 = readline()){
    let line1Arr = line1.split(' ');
    let n = parseInt(line1Arr[0]);
    let q = parseInt(line1Arr[1]);
     
    let arr = readline().split(' ').map((it)=>parseInt(it));
    for(let i=0;i<q;i++){
        let x = parseInt(readline());
        let count = 0;
        arr.forEach((val,index)=>{
            if(val >= x){
                count++;
                arr[index] = --val;
            }
        })
        print(count);
    }
}
用js总是通不过是为什么啊，我实在是看不出有什么问题？？