E - Set Meal
https://atcoder.jp/contests/abc331/tasks/abc331_e
思路
定义 vector<int> v[100005];
对于 c d 对进行group操作, 得到每个ai dish 对应不可能的 bj dish的cost值的集合
对b dish cost数组进行排序, 小的在前,大的在后,
对于每一个a dish, 使用v寻找第一个排除 “此dish对应不可能的 bj dish的cost值的集合 ”后的 最大cost值, 更新到 max_ab_product.
Code
https://atcoder.jp/contests/abc331/submissions/48194364
int N,M,L; int a[100005], b[100005]; vector<int> v[100005]; int main() { cin >> N >> M >> L; for(int i=1; i<=N; i++){ cin >> a[i]; } for(int i=1; i<=M; i++){ cin >> b[i]; } for(int i=1; i<=L; i++){ int c, d; cin >> c >> d; v[c].push_back(b[d]); } for(int i=1;i<=N;i++){ sort(v[i].begin(),v[i].end()); // reverse(v[i].begin(),v[i].end()); } sort(b+1,b+M+1); int max_ab_product=-1; for(int i=1;i<=N;i++){ int ai = a[i]; // cout << "i=" << i << "; ai=" << ai << endl; for(int j=M;j;j--){ int bj = b[j]; cerr << "bj=" << bj << endl; bool bj_invalid = false; for(int k=0; k<v[i].size(); k++){ // cout << "k=" << k << "; val=" << v[i][k] << endl; if (v[i][k] == bj){ v[i].erase(v[i].begin()+k); bj_invalid = true; break; } } if (bj_invalid){ // compare with next biggest bj continue; } // valid bj found int product = ai + bj; if (max_ab_product < product) { max_ab_product = product; } // cout << "i=" << i << "; j="<< j << endl; // cout << "ai=" << a[i] << "; bj="<< b[j] << endl; // cout << "product = " << product << endl; break; } } cout << max_ab_product << endl; return 0; }
标签:Set,int,abc331,100005,cost,dish,Meal From: https://www.cnblogs.com/lightsong/p/17876146.html