21天好习惯 第2天 差分数组

21天好习惯 第2天 差分数组 21天零基础入门ACM 21天零基础入门ACM之 第2天 差分数组 题目：

链接：https://ac.nowcoder.com/acm/problem/209813

代码：

class Solution {
public:
    
    int oddnumber(int n, int m, vector& l, vector& r) {
        // write code here
        int ans=0;
        int nums[200005];
        memset(nums, 0, sizeof(nums));
        nums[0]=m;
        for(int i=0;i 
题目2： 
链接：https://ac.nowcoder.com/acm/contest/21592/L
 

 
 
 
题意： 
给你n条线段，让你求出有多少个单位的x的区间，被这些线段所覆盖。
 
思路： 
用差分数组记录每个区间被覆盖过几次，在统计有覆盖过的区间。
 
python代码如下：
 
t = int(input())
arr = [0]*100005
for i in range(t):
    a,b,c,d=map(int,input().split())
    arr[a+1]+=1
    arr[c+1]-=1
ans = 0
for i in range(1,100005):
    arr[i]+=arr[i-1]
    if arr[i]>0:
        ans+=1
print(ans)
 
c++ 代码如下：
 
#include
using namespace std;
const int N=1000010;
typedef long long ll;
 
int a[N];
 
int main(){
    int x1,x2,y1,y2,n;
    memset(a, 0, sizeof(a));
    cin>>n;
    while(n--){
        cin>>x1>>y1>>x2>>y2;
        a[x1+1]+=1;
        a[x2+1]-=1;
    }
    int ans=0;
    for(int i=1;i<=1000000;i++){
        a[i]=a[i-1]+a[i];
        if(a[i]) ans++;
    }
    cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/4830138.html