滴滴4.10机试编程题小结
第一题贪心算法过了30%
题目大体：同一时刻给定一些进程准备时间，运行时间，进程只有在准备好后才能运行，求运行完所有进程所需的最短时间？
贪心策略：越早结束的进程先运行，结束时间相同的进程优先执行运行时间长的进程。
过了30%说明想法不完善
以下是代码：
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
using namespace std;
bool cmp(int a,int b){return a>b;}
int main(){
int n=0;
cin>>n;
vector<int> nums(n,0);
multimap<int,int> map1;
int i=0;
int finish=0;
for(int i=0;i<n;i++){
int a=0,b=0;
cin>>a>>b;
map1.insert(pair<int,int>(a+b,b));
}
auto iter=map1.begin();
int prev=iter->first;
while(iter!=map1.end()){
vector<int> temp;
while(iter->first==prev){
temp.push_back(iter->second);iter++;
}
sort(temp.begin(),temp.end(),cmp);
finish=prev>finish?prev:finish;
for(int i=1;i<temp.size();i++){
finish+=temp[i];
}
prev=iter->first;
}
cout<<finish<<endl;
return 0;
}
第二题动态规划过了91%
实质上就是求最长的等差数列长度，要注意对于i位置的a[i]有a[i]>x*i，因为题中说只能改成正数，所以a[i]至少能够保证以a[i]为结尾的等差数列第一个数是正数。
dp[i]:以i为结尾的最大等差数列长度
dp[i]=if(nums[i]-nums[j]==x*(i-j)&&a[i]>i*x){max(dp[j]+1);}
剩下的9%时间超了。。。
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n=0,x=0;
cin>>n>>x;
vector<int> nums(n,0);
for(int i=0;i<n;i++){
cin>>nums[i];
}
vector<int> dp(n,0);
dp[0]=1;
for(int i=1;i<n;i++){
dp[i]=1;
int max1=1;
for(int j=0;j<i;j++){
if(nums[i]-nums[j]==x*(i-j)&&(nums[i]-x*i)>0){
max1=max1>(dp[j]+1)?max1:(dp[j]+1);
}
}
dp[i]=max1>dp[i]?max1:dp[i];
}
int length=0;
for(int i=0;i<n;i++){
length=length>dp[i]?length:dp[i];
}
cout<<n-length<<endl;
return 0;
} 
