2015年4月30日 星期四

[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':' ') ;
}
 

沒有留言:

張貼留言