P1023 税收与补贴问题

神题啊，题面读不懂

但是难以置信的是暴力出奇迹（Ac）了

感谢大佬

------------------------------------

链接：Miku

不等式，不存在的，我们只需要首先做出来一个价格表，统计一下从最小已知售价到最大已知售价后到销量为零后

的所有价钱--销量关系

然后从小到大暴力枚举所有可能的税收/补贴

过了？？？

过了

注意，第四个点中有两个一样的最大值，所以说这么干的时候要用>=判断（当然不太正经，这纯属是因为第二个最大值在期望价前面）

然后就过了

#include<iostream>
#include<cstdio>
#include<algorithm> 
using namespace std;
const int limit=100001;
int pr[limit],num[limit];
int goal,k;
int countt;
int x;
int kk;
int w;
int ans;
int ansx;
int place;
int tim;
int main(){
    scanf("%d",&goal);
    while(cin>>pr[++countt]&&cin>>num[countt]&&(pr[countt]!=-1&&num[countt]!=-1)){//暴力制表
        if(pr[countt]!=pr[countt-1]+1&&countt>1){
            kk=(num[countt-1]-num[countt])/(pr[countt]-pr[countt-1]);
            x=pr[countt];
            for(int i=pr[countt-1]+1;i<=x;++i){
                pr[countt]=i;
                num[countt]=num[countt-1]-kk;
                countt++;        
            }
            --countt;
        }
    }
    scanf("%d",&k);
    countt--;
    while(num[countt]>0){
        countt++;
        pr[countt]=pr[countt-1]+1;
        num[countt]=num[countt-1]-k;
    }
    countt--;
    for(int i=1;i<=limit;++i){//暴力出奇迹
        w=-0x3f;
        tim=0;
        for(int j=1;j<=countt;++j){
            x=(pr[j]-pr[1]+i)*num[j];
            if(x>=w){
                tim=1;    
                w=x;
                place=pr[j];
            }
        }
        if(place==goal){
            cout<<i;
            return 0;
        }
        w=-0x3f;
        for(int j=1;j<=countt;++j){
            x=(pr[j]-pr[1]-i)*num[j];
            if(x>=w){
                w=x;
                place=pr[j];
                tim=1;
            }
        }
        if(place==goal){
            cout<<i*-1;
            return 0;
        }
    }    
    cout<<"NO SOLUTION";
    return 0;
}

Ac'

发送评论 编辑评论

发送评论编辑评论