拼多多-笔试记录（7月28日）
@TOC
problem1 几何严格单调递增数组
问题
给定两个数组nums1, nums2, 其中nums1几何严格单调递增，判断能否从nums2中找一个数替换掉nums1中的一个数，使得nums1严格单调递增。如果可以的话，求出可用于替换的nums2中的最大数，否则输出"NO"。（注：几乎严格单调递增指的是除了仅有的一个位置以外，其余所有位置均是严格单调递增的）
分析
几乎严格单调递增数组可以分为两段，两段分别严格单调递增。可以先找出不严格单调递增的位置pivot，则只能通过修改nums1[pivot]或者nums1[pivot-1]即可使其严格单调递增
代码
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<algorithm>
#include<map>
using namespace std;
void getAns(vector<int> &nums1, vector<int> &nums2){
//step1 寻找pivot
int n = nums1.size();
int pivot = -1;
for(int i=1; i<n; i++){
if(nums1[i]<=nums1[i-1]){
pivot = i;
break;
}
}
// 做法
sort(nums2.begin(), nums2.end()); //预排序，方便调用二分搜索，虽然复杂度高了，但代码简单点
// 如果修改nums1[pivot]
pair<int,int> ans(-1,-1);
if(pivot+1>=nums1.size() || nums1[pivot+1]>nums1[pivot-1]){
auto ite1 = upper_bound(nums2.begin(), nums2.end(), nums1[pivot-1]);
int end = 0x7fffffff;
if(pivot+1<nums1.size()) end = min(end, nums1[pivot+1]);
auto ite2 = lower_bound(nums2.begin(), nums2.end(), end);
if(ite2-ite1!=0){
ite2--;
ans = make_pair(pivot, *ite2);
cout<<*ite2<<endl;
}
}
// 如果修改nums1[pivot-1]
if(pivot-2<0 || nums1[pivot-2]<nums1[pivot]){
int start = 0x80000000;
if(pivot-2>=0) start = max(start, nums1[pivot-2]);
auto ite1 = upper_bound(nums2.begin(), nums2.end(), start);
auto ite2 = lower_bound(nums2.begin(), nums2.end(), nums1[pivot]);
if(ite2-ite1!=0){
ite2--;
if((*ite2)>ans.second){
ans.first = pivot-1;
ans.second = *ite2;
}
}
}
if(ans.first==-1) cout<<"NO"<<endl;
else{
nums1[ans.first] = ans.second;
for(auto val : nums1) cout<<val<<' ';
cout<<endl;
}
}
int main(){
/* 测试样例
* inpu
* 1 3 7 4 10
* 2 1 5 8 9
* output:
* 1 3 7 9 10
*/
string line;
getline(cin, line);
istringstream strin(line);
int tmp;
vector<int> nums1;
while(strin>>tmp) nums1.push_back(tmp);
strin.clear();
getline(cin, line);
strin.str(line);
vector<int> nums2;
while(strin>>tmp) nums2.push_back(tmp);
getAns(nums1, nums2);
return 0;
}problem2 字符串数组组环
问题
给定一个字符串数组，问能否通过调整这些字符串数组中元素的位置，使得其可以围城一个环，如果可以输出true，否则输出false。注：相邻两个字符串的邻接字母要相同
分析
step1 可以把原问题转化为图，如果两个字符串可以紧邻，说明他们之间存在这边。
step2 遍历图，是否可以存在一种遍历方式，经过遍历后，第一个字符串的第一个元素与最后一个字符串的最后一个元素相同，如果可以则存在环，否则不存在。
遍历图可以考虑dfs搜索，同时由于是要看是否有环，所以任意一个字符串均可以作为遍历的第一个元素，不妨以字符串数组中的一个元素作为开始
结果：只通过了95%，但是听讨论区的意见，好像该方法是对的，是测试样例的问题
代码
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<algorithm>
#include<map>
using namespace std;
bool dfs(char start, char cur, vector<bool> &flag, vector<string> &nums, map<char, vector<int>> &charMap, int k){
if(k==0){
return cur==start;
}
for(auto val : charMap[cur]){
if(flag[val]==false){
flag[val] = true;
if(dfs(start, *nums[val].rbegin(), flag, nums, charMap, k-1)) return true;
flag[val] = false;
}
}
return false;
}
int main(){
/* 测试样例
* Input: CAT TIGER RPC
* Output: true
*/
string line;
getline(cin, line);
istringstream strin(line);
vector<string> nums;
map<char, vector<int>> charMap;
string tmp;
while(strin>>tmp){
nums.push_back(tmp);
charMap[tmp[0]].push_back(nums.size()-1);
}
vector<bool> flag(nums.size(), false);
flag[0] = true;
bool ans = dfs(nums[0][0], *nums[0].rbegin(), flag, nums, charMap, nums.size()-1);
if(ans==true){
cout<<"true"<<endl;
}else{
cout<<"false"<<endl;
}
return 0;
}problem3 最小平均响应时间安排
问题
0时刻，某人收到了N个工作，完成每个工作所需的时间为，工作的完成存在先后的依赖关系（即某些工作必须在其它工作之前完成）。一个人顺序完成N个工作，问如何安排完成工作的顺序，使得完成工作的平均响应时间最短，输出这样的顺序，在满足平均响应时间最短的情况下，要求字典序最小？（响应时间：从接收到工作到工作完成的时间）
分析
问题乍一看，拓扑排序，不过要求最短响应时间，当初以为是树形dp，直接放弃了，看了大家的分析，可后悔死人了，我想哭，可是我要假装坚强
说一下其他人的做法：拓扑排序+优先队列，对于当前可以处理的工作，优先选择完成时间最少的工作，如果存在多个完成时间最少的工作，选择编号最小点工作。
原因：可以先想想，如果没有依赖性的话，你会怎么做？肯定是希望等待时间最少，即所需时间少的工作优先完成（同时需要考虑字典序尽可能小）。现在是在它的基础上加了依赖性，每次能够只能当前没有前驱的工作集合中挑选用时最少的工作。也就是相比于无依赖性的时候，候选集合变小了，但是还是类似的思路，所以可以直接用优先队列挑选用时最少的工作
代码
测试样例忘了，只测了简单的样例
3 2
1 2 3
2 1
1 0
2,1,0,
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
struct Cmp{
bool operator()(const pair<int,int> &x, const pair<int,int> &y) const{
// 实现大于号， <first,second>分别表示cost, 编号
return x.second>y.second || (x.second==y.second && x.first>y.first);
}
};
int main(){
int N, M; cin>>N>>M;
vector<int> cost(N);
for(int i=0; i<N; i++) cin>>cost[i];
vector<int> indegree(N,0);
vector<vector<int>> edges(N);
for(int i=0; i<M; i++){
int prev, next; //假设输入依赖时工作编号从0开始
cin>>prev>>next;
indegree[next]++;
edges[prev].push_back(next);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, Cmp> pque;
for(int i=0; i<N; i++){
if(indegree[i]==0){
pque.push(make_pair(cost[i], i));
}
}
vector<int> ans;
while(!pque.empty()){
auto node = pque.top(); pque.pop();
ans.push_back(node.second);
for(auto val : edges[node.second]){
indegree[val]--;
if(indegree[val]==0) pque.push(make_pair(cost[val], val));
}
}
// 输出安排结果
for(auto val : ans) cout<<val<<',';
cout<<endl;
return 0;
}problem4 最高金字塔
问题
给定N个积木，长宽均相等为，高度为1，重量为
，利用积木来搭金字塔，要求：每一层只有一块积木，上一层的积木的大小要严格小于当前层的积木的大小，每一层只能承受不大于自身重量的7倍的积木。问题金字塔最高能搭多少层？
分析
当高处的层确定后，高处层的具体配置我们并不关心，有无后效性，可以考虑动态规划
原问题N比较小，重量比较大，考虑用N相关的变量来描述状态
为了减少计算量，提前对积木按照由小到大的排序排序
状态： dp[i][j]表示第i个积木为底时，构造高度为j时所用的积木的最小重量
状态转移方差：dp[i][j] = min(dp[i][j], dp[k][j-1]+)（前提dp[k][j-1]状态合法，且第k个积木尺寸小于第i个积木
结果：代码只通过了95%，问题应该出在时间复杂度O(n^3)上
代码
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<algorithm>
#include<map>
using namespace std;
int main(){
int N; cin>>N;
vector<pair<int,int>> nums(N);
for(int i=0; i<N; i++) cin>>nums[i].first;
for(int i=0; i<N; i++) cin>>nums[i].second;
nums.push_back(make_pair(0,0));
sort(nums.begin(), nums.end(), less<pair<int,int>>());
const int M = 0x7fffffff;
vector<vector<int>> dp(N+1, vector<int>(N+1,M));
dp[0][0] = 0;
// dp[i][j]表示第i个积木为底时，构造高度为j时所用的积木的最小重量
int ans = 0;
for(int i=1; i<=N; i++){
// 以第i块积木为低时
for(int k=0; k<i; k++){
if(nums[k].first<nums[i].first){ //长度满足条件
for(int j=0; j<=k; j++){
if(dp[k][j]!=M && dp[k][j]<=nums[i].second*7){
dp[i][j+1] = min(dp[i][j+1], dp[k][j]+nums[i].second);
ans = max(ans, j+1);
}
}
}
}
//for(int j=0; j<=i; j++) cout<<dp[i][j]<<' ';
//cout<<endl;
}
cout<<ans<<endl;
return 0;
}
百度成长空间 414人发布
