//

//有三种升级技能的策略：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
     
       a; 9 int t[100005][3];10 vector
      
       
         > t1;11 vector
        
         
          
            > > t2;12 vector
           
            
              > t3;13 vector
             
              
                > 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\n", t1[i].first, t1[i].second);44 for(j = 0; j < t2[i].size(); ++j)45 printf("t2 %d %d\n", t2[i][j].first, t2[i][j].second);46 }47 for(i = 0; i < t3.size(); ++i)48 printf("t3 %lf %d\n", 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\n", 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\n", 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\n", 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("\n");78 }79 }