[CF 521D] Shop

作法：

首先不難證明，對於同一個技能來說，如果三種操作都作用在他身上了，那麼順序一定會是第1種 -> 第2種 -> 第3種。並且第1種只會進行一次。再來因為我們要讓總乘積越大越好，也就是個別技能的成長倍數越大越好，所以可以先把所有數分開來看，最後再合併起來。首先考慮如果對於一個數字，有三種操作可以選擇，那麼第3種一定是最後執行，並且選的時候會按照乘的倍數由高到低一個一個選。至於第1種和第2種操作，假設當前數字為 x ，第1種操作可以把 x 設為 b ( 這裡假定 b > x ，否則就完全不用理這個操作了 )，而第2種操作則是有很多個，分別是把 x 加上 b_1 , ... , b_k ，並且可以假設這些數已經由大到小排好了，因為不管怎麼樣，取加的數比較多的會比較好。再來我們要決定在選取這些操作的時候，第1種操作應該要被放在哪個時間點來選( 也就是當我們能夠在這個數字上花的操作次數越來越多時，一般來說我們會依次取 b_1 , b_2 , ... ，但當能夠對這個數操作 k+1 次時，一定是把那兩種操作都取掉了，因此中間一定有一個瞬間是取完 b_i 之後取了第1種操作 )。令 y = b - x ，事實上我們可以把這個第1種操作看成「第2種操作的加上 y 」，因為當一選取到第1種操作時，一定是在執行所有加的操作之前就先執行他了，也就是執行他的時候 x 的值還沒被改過，因此他就可以被等價成「第2種操作的加上 y」 。這邊比較容易搞混的是，雖然這個第1種操作的「優先度」比較低（也就是當我們只能在這個數上花少少的次數的時候，還輪不到他被取到），但當一決定取他的時候，就會把他放到所有操作的最前面來執行，所以才能斷定他就等價於「第2種操作的加上 y 」。

因此現在我們把第1種操作都改為第2種操作了，這時候的想法也跟剛才類似，因為當我們取到 b_i 的時候，代表 b_1 ~ b_( i-1 ) 都已經被取到了，因此此時產生的數的值一定會是 x + b_1 + ... + b_( i-1 ) ，那麼再取 b_i 就會讓值變為 x + b_1 + ... + b_i ，因此這個操作的作用是已知的，也就是他讓這個數成長的倍率也是已知的，那麼也就可以把他等價成第3種操作了。因此現在全部都只剩第3種操作了，那麼就可以直接按照倍率由大到小排序然後 greedy 了。（注意到在把第2種操作轉換為第3種時，每次多加了一個 b_i 的時候，其實這個數的成長倍率是遞減的，因為這個數越來越大，但加的數越來越小。因此在 greedy 的時候不會發生「 b_i 被取到的時候，b_1 ~ b_( i-1 ) 還有沒被取到的」的情況。）

code :

#include<bits/stdc++.h>
#define DB double
#define pdi pair<DB,int>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxn=200000+10 ;
 
int type[maxn] ;
vector<pdi> v ;
 
int a[maxn],Set[maxn],id[maxn] ;
vector<pii> add[maxn] ;
vector<int> ans ;
main()
{
    int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    memset(Set,-1,sizeof(Set)) ;
    for(int i=1;i<=m;i++)
    {
        int t,p,b ; scanf("%d%d%d",&t,&p,&b) ;
        type[i]=t ;
        if(t==1 && b>Set[p]) Set[p]=b , id[p]=i ;
        else if(t==2) add[p].push_back((pii){b,i}) ;
        else if(t==3) v.push_back((pdi){(DB)b,i}) ;
    }
    for(int i=1;i<=n;i++) if(Set[i]!=-1 && Set[i]>a[i])
        add[i].push_back((pii){Set[i]-a[i],id[i]}) ;
    for(int i=1;i<=n;i++) if(!add[i].empty())
    {
        sort(add[i].begin(),add[i].end(),greater<pii>()) ;
        DB now=a[i] ;
        for(auto j : add[i])
        {
            DB now2=now+j.F ;
            v.push_back((pdi){now2/now,j.S}) ;
            now=now2 ;
        }
    }
 
    sort(v.begin(),v.end(),greater<pdi>()) ;
    for(int i=0;i<k && i<v.size();i++)
        ans.push_back(v[i].S) ;
 
    printf("%d\n",ans.size()) ;
    int cnt=0 ;
    for(auto i : ans) if(type[i]==1)
        printf("%d%c",i,++cnt==ans.size()?'\n':' ') ;
    for(auto i : ans) if(type[i]==2)
        printf("%d%c",i,++cnt==ans.size()?'\n':' ') ;
    for(auto i : ans) if(type[i]==3)
        printf("%d%c",i,++cnt==ans.size()?'\n':' ') ;
}