思维的体操

脑洞扩容计划

LA3266
田忌赛马
一开始想到的错误做法就是从小到大排序,肛得过的直接肛,肛不过的直接牺牲怼最强,再倒过来一次处理,然而WA...
应该把能肛的上下等马分批处理,不能互怼的再牺牲择优

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+11;
typedef long long ll;
ll a[maxn],b[maxn],n;
int main(){
    ios::sync_with_stdio(0);
    while(cin>>n){
        if(n==0) break;
        for(int i = 0; i < n; i++) cin>>a[i];
        for(int i = 0; i < n; i++) cin>>b[i];
        sort(a,a+n);sort(b,b+n);
        int l1=0,r1=n-1,l2=0,r2=n-1;
        ll ans=0;
        for(int i = 0; i < n; i++){
            if(a[l1]>b[l2]){//下等马VS下等马 
                l1++;l2++;
                ans+=200;
            }
            else if(a[r1]>b[r2]){//上等马VS上等马 
                r1--;r2--;
                ans+=200;
            }
            else if(a[l1]<b[r2]){//下等马VS上等马 
                l1++;r2--;
                ans-=200;
            }
            else{
                l1++;r2--;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

CodeForces - 801C
二分不是问题,就是想到C(x)的实现时卡壳了
还有C(∞)的用法就是简单粗暴好使
注意r不要开太大,精度救不了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+11;
const double oo = 1e12;
int a[maxn],b[maxn],n,p,tmp;
bool C(double x){//没有一个没电 
    double E=x*p;
    for(int i = 0; i < n; i++){
        double e=b[i]-a[i]*x;//总损耗 
        if(e<0) E+=e;//NOTE 别想太复杂 
        if(E<0) return 0;
    }
    return 1;
}
int main(){
    while(scanf("%d%d",&n,&p)!=EOF){
        for(int i = 0; i < n; i++){
            scanf("%d%d",&a[i],&b[i]);
        }
        if(C(oo)){
            printf("-1\n");
            continue;
        }
        double l=0,r=oo,mid;
        for(int i = 0; i < 100; i++){
            mid = l+(r-l)/2;
            if(C(mid)) l=mid;
            else r=mid;
        }
        printf("%.10lf\n",mid);
    }
    return 0;
}

POJ2828
逆序处理
改造线段树以支持动态区间问题(维护当前区间还剩多少位子)
真TM机智啊,我还以为一定要伸展树什么的
需要注意右子树查询时k的变化

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 2e5+11;
int ans[maxn]; 
struct ST{
    int val[maxn<<2];
    void pu(int o){
        val[o]=val[o<<1]+val[o<<1|1];
    }
    void build(int o,int l,int r){
        if(l==r){
            val[o]=1;
            return; 
        }
        int m=l+r>>1;
        build(o<<1,l,m);
        build(o<<1|1,m+1,r);
        pu(o);
    }
    void update(int o,int l,int r,int k,int v,int key){
        if(l==r){
            val[o]+=v;//占位v=-1
            ans[l]=key; 
            return; 
        }
        int m=l+r>>1;
        if(val[o<<1]>=k) update(o<<1,l,m,k,v,key);//还够位子 
//        else update(o<<1|1,m+1,r,k,v,key);
        else update(o<<1|1,m+1,r,k-val[o<<1],v,key);
        pu(o);
    }
}st;
int n,pos[maxn],val[maxn];
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i = 0; i < n; i++){
            scanf("%d%d",&pos[i],&val[i]);
            pos[i]++;
        }
        st.build(1,1,n);
        for(int i = n-1; i >= 0; i--){
            st.update(1,1,n,pos[i],-1,val[i]); 
        }    
        for(int i = 1; i <= n; i++){
            if(i==n)printf("%d\n",ans[i]);
            else printf("%d ",ans[i]);
        }
    }
    return 0;
}

LA7183
硬币部分存在约数关系,唯一蛋疼就是20 50 200 500,那不妨把50塞到100(2张一起用),同理500塞到1000,然后mark一下原来50和500的张数,计算时乘2,还有一点瑕疵是50和500可能各存在剩下的奇数1,枚举用和不用
网上的通解:取反,贪心策略中要从大到小贪并尝试每种减少1枚硬币,真简洁啊...

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2;
typedef long long ll;
const ll oo = 0x3f3f3f3f3f3f3f3f;
ll coin[]={1,5,10,20,50,100,200,500,1000,2000};
ll num[maxn],c[maxn];
ll ans;
void dfs(int i,ll cnt,ll t){//t
    if(cnt==0){
        ans=min(ans,t);
        return;
    }
    if(i<0){
        return;
    }
    c[i]=min(cnt/coin[i],num[i]);//当前硬币做多能取的数目 
    dfs(i-1,cnt-coin[i]*c[i],t+c[i]);
    if(c[i]>0){
        c[i]--;//少拿一个 
        dfs(i-1,cnt-coin[i]*c[i],t+c[i]);
    } 
}
int main(){
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while(T--){
        ll p,tot,sum;tot=sum=0;
        cin>>p;
        for(int i = 0; i < 10; i++){
            cin>>num[i];
            sum+=coin[i]*num[i];
            tot+=num[i];
        }
        ll cnt=sum-p;
        if(cnt<0){
            cout<<-1<<endl;
            continue;
        }
        ans=oo;
        dfs(9,cnt,0);
        if(ans==oo) cout<<-1<<endl;
        else cout<<tot-ans<<endl;
    }
    return 0;
}

标签: 算法, 学习

添加新评论