Office Keys

首先显然有随人位置的递增，钥匙的位置也要递增，这样考虑两张做法：

1.$f(i,j)$ 表示前i个人，钥匙到第j个最少用的最大时间，然后$O(nK)$ dp

2.二分时间，对于每一个人选择当前能选择的最左面的钥匙 $O((n+K) logn)$

#include 
      
       #define LL long longconst int N = 2010;using namespace std;int n,m,pre[N],a[N],b[N];int Abs(int x){    if(x<0) return -x;    return x;}int p;bool check(int tim){    int j = 1;    for(int i=1;i<=n;i++)    {        while(j<=m && Abs(a[i]-b[j])+(LL)Abs(b[j]-p) > tim) j++;        if(j>m) return 0;        else j++;    }    return 1;}int main(){    int maxv = 0;    scanf("%d%d%d",&n,&m,&p);    maxv = p;    for(int i=1;i<=n;i++) scanf("%d",&a[i]), maxv = max(maxv ,a[i]);    for(int i=1;i<=m;i++) scanf("%d",&b[i]), maxv = max(maxv, b[i]);    sort(a+1,a+n+1);    sort(b+1,b+m+1);    int l=0, r=0;    for(int i=1;i<=n;i++) l = max(l, Abs(p-a[i]));    for(int i=1;i<=n;i++) r = max(r, Abs(b[i]-a[i]) + Abs(p-b[i]));    while(r-l>5)    {        int mid = (l+(LL)r)>>1LL;        if(check(mid)) r = mid;        else l = mid;    }    for(int i=l;i<=r;i++)        if(check(i))        {            cout<
       <
      

 

Cards Sorting

方法1：直接用splay模拟。

方法2：考虑每次删掉当前最小数的代价是上一个最小数和它之间的循环dist，BIT或链表即可。

(取自CF)

 

#include 
      
       const int N = 100010;#define INF 0x3f3f3f3f#define LL long longusing namespace std;struct node{    node *ch[2];    int v, sum, minv;    int cmp(int x)    {        if(ch[0]->sum + 1 == x) return -1;        return x > ch[0]->sum;    }    node* init(int x);    void update()    {        sum = ch[0]->sum + ch[1]->sum + 1;        minv = min(v, min(ch[0]->minv, ch[1]->minv));    }}spT[N], Null, *root; int tot=0; node* node::init(int x){    v=x;    minv=x;    ch[0]=ch[1]=&Null;    sum=1;    return this;} node* build(int src[],int l,int r){    if(l==r) return spT[++tot].init(src[l]);    int mid=(l+r)>>1;    node* tmp=spT[++tot].init(src[mid]);    if(l
       
        ch[0]=build(src,l,mid-1);    if(mid
        
         ch[1]=build(src,mid+1,r);    tmp->update();    return tmp;} void rot(node* &o,int x){    node* tmp=o->ch[x];    o->ch[x]=tmp->ch[x^1];    tmp->ch[x^1]=o;    o->update();    o=tmp;    o->update();} void splay(node* &o,int k){    int t=o->cmp(k);    if(t==-1) return;    if(t) k-=o->ch[0]->sum+1;    int t1=o->ch[t]->cmp(k);    if(~t1)    {        if(t1) k-=o->ch[t]->ch[0]->sum+1;        splay(o->ch[t]->ch[t1],k);        if(t1==t) rot(o,t);        else rot(o->ch[t],t1);    }    rot(o,t);}int find_min(node *&o,int minv,int now){    if(o->ch[0]->minv == minv) return find_min(o->ch[0],minv,now);    else    {        if(o->v == minv) return now+o->ch[0]->sum;        return find_min(o->ch[1],minv,now+o->ch[0]->sum+1);    }}int n,a[N];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&a[i]);    Null.minv = INF;    a[0]=INF;    a[n+1]=INF;    root = build(a,0,n+1);    int len = n+2;    LL ans = 0;    for(int i=1;i<=n;i++)    {        int tmp = find_min(root,root->minv,0);        ans += (LL)tmp;        splay(root,1);        splay(root->ch[1],tmp+1);        node* tp = root->ch[1]->ch[0];        root->ch[1]->ch[0] = &Null;        root->ch[1]->update();        root->update();                splay(tp,tp->sum);        tp = tp->ch[0];        len--;                splay(root,len-tp->sum);        splay(root->ch[0],len-tp->sum-1);        root->ch[0]->ch[1] = tp;        root->ch[0]->update();        root->update();    }    cout << ans << endl;    return 0;}
        
       
      

 

Bamboo Partition

显然要满足的条件等价于

$\sum_{i=1}^n { [\frac{a_i + d - 1}{d}] \cdot d - a_i} \leq K$

$F(d) = \sum_{i=1}^n { [\frac{a_i - 1}{d}] + 1} \cdot d  \leq K + \sum {a_i}$

固定 $\sum_{i=1}^n { [\frac{a_i - 1}{d}] + 1}$，从而 $F(d)$ 单调。

对于前者直接找出所有得数相同的 $d$ 的区间，逐一计算即可。

复杂度$O(n^2 \sqrt {a_i} )$

通过调参可以 $O(n \sqrt {a_{max} n})$

#include 
      
       #define LL long longconst int N = 110;using namespace std;int n,tot,a[N];LL K;vector
       
         v;int main(){    cin>>n>>K;    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);        K += (LL)a[i];        int j=1;        int tmp = a[i]-1;        if(tmp>0)        {            for(int i=1;i<=tmp;i=j+1)                j = tmp/(tmp/i), v.push_back(i);            v.push_back(tmp+1);        }    }    v.push_back(1);    sort(v.begin(),v.end());    v.resize(distance(v.begin(), unique(v.begin(), v.end())));    LL ans = 1, sum;    for(int i=0;i<(int)v.size() - 1;i++)    {        int l = v[i], r = v[i+1]-1;        sum = 0;        for(int j=1;j<=n;j++) sum += (a[j]-1LL)/l + 1LL;        LL tmp = min(K/sum, (LL)r);        if(tmp>=l) ans = tmp;    }    LL l = v[v.size()-1];    LL tmp = K/n;    if(tmp >= l) ans = tmp;    cout << ans << endl;}