L3-2 还原文件 (30 分)【2021天梯赛】测附试点2分析

迷南。 2023-01-17 07:58 56阅读 0赞

**这道题比赛时直接全部以字符串格式存进去中，然后用字符串的find函数寻找每个纸条在另外半张纸上的位置，然后按照位置排序输出，嗯，思路很简单，代码也很简单，骗到了26分，但是测试点2是过不了的。**

## 【26分代码】 ##

#include <iostream>
    #include <algorithm>
    using namespace std;
    struct node{
        
    	string s;
    	int num;       //字条编号 
    	int t;         //字条位置 
    };
    bool cmp(node a, node b) {
        
    	return a.t < b.t;
    }
    int main() {
        
    	int n;
    	cin >> n;
    	getchar();
    	string str;
    	getline(cin, str);
    	int m;
    	cin >> m;
    	getchar();
    	node a[m];
    	for(int i = 0; i < m; i++) {
        
    		int k;
    		cin >> k;
    		getchar();
    		string t;
    		getline(cin, t);
    		a[i].num = i+1;
    		a[i].s = t;
    	}
    	for(int i = 0; i < m; i++) {
        
    		a[i].t = str.find(a[i].s);
    	}
    	sort(a, a+m, cmp);
    	for(int i = 0; i < m; i++) {
        
    		if(i) cout << " ";
    		cout << a[i].num;
    	}
    }

## AC代码 ##

**测试点二是可能出现一个纸条在str中出现两次的情况，直接用find函数会返回第一次出现的位置，但这样明显是不对的，比如断口 `1 2 3 1 2`，有两个纸条`1 2 3`和`1 2`用find函数搜索返回的都是0。**

**感觉这个题的测试点可能有问题。。。**

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    struct node{
        
    	string s;
    	int num;
    	int t;
    };
    bool cmp(node a, node b) {
        
    	return a.t < b.t;
    }
    bool cmp1(node a, node b) {
        
    	return a.num > b.num;
    }
    
    int main() {
        
    	int n;
    	cin >> n;
    	getchar();
    	string str;
    	getline(cin, str);
    	int m;
    	cin >> m;
    	getchar();
    	node a[m];
    	for(int i = 0; i < m; i++) {
        
    		int k;
    		cin >> k;
    		getchar();
    		string t;
    		getline(cin, t);
    		a[i].num = i+1;
    		a[i].s = t;
    	}
    	sort(a, a+m, cmp1);
    	//cout << str << endl;
    	for(int i = 0; i < m; i++) {
        
    		int x = str.find(a[i].s);
    		int len = a[i].s.length();
    		a[i].t = x;
    		int num = 0;
    		for(int j = x; ; j++) {
        
    			if(str[j] == ' ') {
        
    				str[j] = '*';
    				num++;
    			}
    			if(num == 2) break;
    		}
    	}
    	sort(a, a+m, cmp);
    	for(int i = 0; i < m; i++) {
        
    		if(i) cout << " ";
    		cout << a[i].num;
    	}
    }

**题目描述：**  
一份重要文件被撕成两半，其中一半还被送进了碎纸机。我们将碎纸机里找到的纸条进行编号，如图 1 所示。然后根据断口的折线形状跟没有切碎的半张纸进行匹配，最后还原成图 2 的样子。要求你输出还原后纸条的正确拼接顺序。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70 1]  
**输入格式：**  
输入首先在第一行中给出一个正整数 N（1<N≤10^5 ），为没有切碎的半张纸上断口折线角点的个数；随后一行给出从左到右 N 个折线角点的高度值（均为不超过 100 的非负整数）。

随后一行给出一个正整数 M（≤100），为碎纸机里的纸条数量。接下去有 M 行，其中第 i 行给出编号为 i（1≤i≤M）的纸条的断口信息，格式为：

K h\[1\] h\[2\] … h\[K\]其中 K 是断口折线角点的个数（不超过 104 +1），后面是从左到右 K 个折线角点的高度值。为简单起见，这个“高度”跟没有切碎的半张纸上断口折线角点的高度是一致的。

**输出格式：**  
在一行中输出还原后纸条的正确拼接顺序。纸条编号间以一个空格分隔，行首尾不得有多余空格。

题目数据保证存在唯一解。

**输入样例：**

17
    95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80
    6
    4 68 58 58 80
    3 81 68 68
    3 95 70 80
    3 68 60 80
    5 80 72 88 81 81
    4 80 97 97 68

**输出样例：**

3 6 1 5 2 4

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70]: /images/20221021/2a206ca87d244271959df8675f8bb97b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70 1]: /images/20221021/6196908c87cb42ca966f5015dc35e1f1.png