洛谷P1631 序列合并

题目描述
有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2N 2个和，求这N^2N 2个和中最小的N个。

这道题除了PE 简直把WA TLE MLE 发挥到了极致
首先不看测试数据 单纯的这道题很简单
读进去两排数据 暴力加法 暴力排序 暴力输出 然后就MLE了

你总不能不让我读数据吧 ？？？
前面两排总还是要有的
但是注意到题目的数据是从大到小给的 也就是说a[0]+b[0]是大于等于a[0]+b[1]和a[1]+b[0]的
换句话说a[i]+b[i]>=a[大于等于i]+b[大于等于j]的

题解很麻烦 不过我没用题解~（人家题解写的很好，表示看不懂）;;;
怎么做表格来着

如果只有b[1]的数据 那么红色为最优解 绿色为最最优解dp[1][1]我们留着输出
!!!不是动态规划我实在想不出什么字母了
我们把这些解放到set里面
为什么 a[i]+b[i]>=a[大于等于i]+b[大于等于j]的
目前最优解是dp[1][2]
好了a[2]+b[2]能小于dp[1][2]==a[2]+b[1]吗刚才说了不可以 ~~~
唯一一个可能对这个解有影响的只有一个数值 dp[2][0]
如果dp[2][0]对<目前set里面的最大值是不是要加入set并且在set里面踢出最大值
我们这样遍历b[2];
遍历？？？没错 TLE
再想 如果dp[2][0]比set里面最大的还要大那我用不用算后面的dp[2][0++]了
没错break
继续操作b[3];
目前我们发现我们的b数组也不用找空间储存了 一个一个读 维护set就可以了

说到这里了 上代码

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <sstream>

using namespace std;

#define MAXN 105

int v1[100001];

int main()
{
	// freopen("data.txt", "r", stdin);

	int T;
	while (cin >> T) {

		//vector<int> v3;
		int a;
		multiset<int, greater<int> > s1;

		for (int i = 0; i < T; i++) {
			scanf("%d", &a);
			v1[i] = a;
		}
		scanf("%d", &a);
		for (int j = 0; j < T; j++) {
			s1.insert(v1[j] + a);
		}
		//sort(v3.begin(), v3.end());
		int temp = *s1.begin();

		for (int i = 1; i < T; i++) {
			scanf("%d", &a);
			for (int j = 0; j < T - i; j++) {
				if (v1[j] + a < temp) {
					s1.erase(s1.begin());
					s1.insert(v1[j] + a);
					temp = *s1.begin();
				}
				else
					break;	//不写break TLE
			}
		}

		multiset<int, greater<int> >::reverse_iterator it1 = s1.rbegin();
		printf("%d", *it1++);

		for (; it1 != s1.rend(); it1++) {
			printf(" %d", *it1);
		}
		printf("\n");

	}


	// freopen("CON", "r", stdin);
	// system("pause");

	return 0;
}

最后附上样例时间