Skip to content

14162: 【原4162】数组相减

题目

题目描述

author: DS TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4162

Description

从一个线性表中删除和另一个线性表完全相同的部分。

Input Format

输入文件三行。

第一行包括两个正整数n,m.(1<=m<=n<=1000)

第二行包括n个用空格分开的int数据,代表第一个线性表的元素。

第三行包括m个用空格分开的int数据,代表需要删除的线性表。

Output Format

输出文件包括一行内容,其中每个数据用空格隔开,代表从第一个线性表中删除了指定线性表后剩下的元素。

Sample Input1

5 2
1 2 3 4 5
3 4

Sample Output1

1 2 5

Sample Input2

11 3
1 2 3 4 5 1 2 3 6 1 2       
1 2 3

Sample Output2

4 5 6 1 2   (解释:线性表1中出现的1 2 3都需要删除, 1 2 则不需要删除。)

Limits

1.保证m<=n。

2.输入格式保证合法。

3.跟第二个线性表完全相同的部分都需要删除,只有部分相同的不需要(见Sample2)。

4.请用一个过程或重载“-”将两个线性表处理为一个新的线性表。

zqy2018's solution

#include <cstdio>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int a[1005], b[1005];
void init(){
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i <= m; ++i)    
        b[i] = read();
}
void solve(){
    for (int i = 1; i <= n; ++i)    {
        bool flag = true;
        for (int j = 1; j <= m; ++j){
            if (i + j - 1 > n || a[i + j - 1] != b[j]) {
                flag = false;
                break;
            }
        }
        if (!flag) printf("%d ", a[i]);
        else i += m - 1;
    }
}
int main(){
    init();
    solve();
    return 0;
}