//521D
//有三种升级技能的策略：1、=； 2、+=；3、*=。最优的升级顺序显然是先使用策略1,再策略2,再策略3
//赋值变加（对于每一种技能只考虑增益最大的赋值操作），加变乘（对于每一种技能优先考虑增益最大的加法），在不超过总升级方案的前提下，排序后选出 m 种所乘系数最大的升级方案。因为再原方案都是乘法方案的情况下，先乘哪个数并不会影响最终结果，所以只需要再将 m 种方案处理成合法的顺序即可（根据策略种类排序；原方案是加法方案同理）
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "vector" 5 #include "utility" 6 #include "algorithm" 7 using namespace std; 8 vector<int> a; 9 int t[100005][3]; 10 vector<pair<int, int> > t1; 11 vector<vector<pair<int, int> > > t2; 12 vector<pair<double, int> > t3; 13 vector<pair<int, int> > sol; 14 int k, n, m; 15 16 int main() 17 { 18 int i, j; 19 scanf("%d%d%d", &k, &n, &m); 20 a.resize(k + 1); 21 t1.resize(k + 1); 22 t2.resize(k + 1); 23 for(i = 1; i <= k; ++i) { 24 scanf("%d", &a[i]); 25 } 26 for(i = 1; i <= n; ++i) { 27 scanf("%d%d%d", &t[i][0], &t[i][1], &t[i][2]); 28 switch(t[i][0]) { 29 case 1: 30 if(t1[t[i][1]].first < t[i][2]) { 31 t1[t[i][1]].first = t[i][2]; 32 t1[t[i][1]].second = i; 33 } 34 break; 35 case 2: 36 t2[t[i][1]].push_back(make_pair(t[i][2], i)); 37 break; 38 case 3: 39 t3.push_back(make_pair(t[i][2], i)); 40 } 41 } 42 /*for(i = 1; i <= k; ++i) { 43 printf("t1 %d %d ", t1[i].first, t1[i].second); 44 for(j = 0; j < t2[i].size(); ++j) 45 printf("t2 %d %d ", t2[i][j].first, t2[i][j].second); 46 } 47 for(i = 0; i < t3.size(); ++i) 48 printf("t3 %lf %d ", t3[i].first, t3[i].second);*/ 49 50 for(i = 1; i <= k; ++i) { 51 if(t1[i].first > a[i]) { 52 t2[i].push_back(make_pair(t1[i].first - a[i], t1[i].second)); 53 //printf("zhuan %d %d ", make_pair(t1[i].first - a[i], t1[i].second).first, make_pair(t1[i].first - a[i], t1[i].second).second); 54 } 55 sort(t2[i].begin(), t2[i].end()); 56 double sum = a[i]; 57 for(j = t2[i].size() - 1; j >= 0; --j) { 58 t3.push_back(make_pair((sum + t2[i][j].first) / sum, t2[i][j].second)); 59 sum += t2[i][j].first; 60 } 61 } 62 sort(t3.begin(), t3.end()); 63 /*for(i = t3.size() - 1; i >= 0; --i) 64 printf("t3 %f %d ", t3[i].first, t3[i].second);*/ 65 66 m = min(m, (int)t3.size()); 67 for(i = t3.size() - 1; i >= (int)t3.size() - m; --i) { 68 sol.push_back(make_pair(t[t3[i].second][0], t3[i].second)); 69 } 70 sort(sol.begin(), sol.end()); 71 printf("%d ", m); 72 if(m) { 73 printf("%d", sol[0].second); 74 for(i = 1; i <= m - 1; ++i) { 75 printf(" %d", sol[i].second); 76 } 77 printf(" "); 78 } 79 }