广联达9.6笔试

编程ak 第一题送外卖求最大利润：dp题，维护两个数组——dp,nextStart,dp[i]表示最后一单为第i单时的最大收益，nextStart[i]表示第i单结束后下一单最小开始时间，需要求和，数据用int会溢出；第二题翻转队列，使所有数一样：因为翻转只能使区间内左边与右边一致，所有最后的数字必然都是最右边的元素，假设为arr[n-1],找到从右往左第一个不等于arr[n-1]的数，模拟翻转过程就好，当不存在不一致的数就Ok了。下面附上两道题代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int main(){
  int n;cin>>n;
  vector<int> s(n);
  for(int i = 0;i < n;i++) cin>>s[i];

  vector<int> t(n);
  for(int i = 0;i < n;i++) cin>>t[i];

  vector<int> a(n);
  for(int i = 0;i < n;i++) cin>>a[i];

  ll ans = INT_MIN;

  vector<ll> dp(n);
  vector<int> nextStart(n);
  for(int i = 0;i < n;i++){
	  dp[i] = a[i];
	  nextStart[i] = s[i] + t[i];
	  for(int j = 0;j < i ;j++){
		  if(nextStart[j] <= s[i]){
			  dp[i] = max(dp[i],dp[j] + a[i]);
		  }
	  }
	  ans = max(ans,dp[i]);
  }
  cout<< ans <<endl;
  //system("pause");
  return 0;
}

#include<bits/stdc++.h>
using namespace std;int ans = 0;
int firstIdx(vector<int>& a,int r,int target){
	int idx = r;
	while(idx >= 0 && a[idx] == target){
		idx--;
	}
	return idx;
}

int main(){
  int n;
  cin>>n;
  
  vector<int> a(n);
  for(int i = 0;i < n;i++) cin>>a[i];
  int finalValue = a.back();
  int r = n-2;
  while(true){
	  int idx = firstIdx(a,r,finalValue);
	  if(idx < 0 ){
		  break;
	  }else{
		  ans++;
	  }
	  r = n - 2 * (n - idx - 1) - 1;
  }
  cout<< ans <<endl;
  // system("pause");
  return 0;
}