【题意】
给定n行数,每行$c_i$个,保证$a_{i,j}<a_{i,j+1}$,现在让你每行选出第$b_i$个元素,这种选择方案记为${b_1,b_2,...,b_n}$,给定m个不能选择的方案,问剩下的方案中和最大为多少
【分析】
先全选最大看合不合法,如果不行给m个依次替换一位找到合法的当中最大的即可
复杂度$O(nmlogm)$
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector <vector<int> > a,b; int n,m; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&n); a.resize(n); for(int i=0;i<n;i++) { int x; scanf("%d",&x); a[i].resize(x); for(int j=0;j<x;j++) scanf("%d",&a[i][j]); } scanf("%d",&m); b.resize(m); for(int i=0;i<m;i++) { b[i].resize(n); for(int j=0;j<n;j++) { scanf("%d",&b[i][j]); b[i][j]--; } } sort(b.begin(),b.end()); vector <int> fin(n); for(int i=0;i<n;i++) fin[i]=int(a[i].size())-1; if(!binary_search(b.begin(),b.end(),fin)) { for(int i=0;i<n;i++) printf("%d ",fin[i]+1); printf("\n"); return 0; } vector <int> res(n,-1); int maxx=0; for(int i=0;i<m;i++) { vector <int> tmp=b[i]; int sum=0; for(int j=0;j<n;j++) sum+=a[j][tmp[j]]; for(int j=0;j<n;j++) if(tmp[j]!=0) { tmp[j]--; if(!binary_search(b.begin(),b.end(),tmp) && sum-a[j][tmp[j]+1]+a[j][tmp[j]]>maxx) { maxx=sum-a[j][tmp[j]+1]+a[j][tmp[j]]; res=tmp; } tmp[j]++; } } for(int i=0;i<n;i++) printf("%d ",res[i]+1); printf("\n"); return 0; }
vector真香啊