P1023 稅收與補貼問題

?

題目背景

每樣商品的價格越低，其銷量就會相應增大。現已知某種商品的成本及其在若干價位上的銷量（產品不會低于成本銷售），并假設相鄰價位間銷量的變化是線性的且在價格高于給定的最高價位后，銷量以某固定數值遞減。（我們假設價格及銷售量都是整數）

對于某些特殊商品，不可能完全由市場去調節其價格。這時候就需要政府以稅收或補貼的方式來控制。（所謂稅收或補貼就是對于每個產品收取或給予生產廠家固定金額的貨幣）

題目描述

你是某家咨詢公司的項目經理，現在你已經知道政府對某種商品的預期價格，以及在各種價位上的銷售情況。要求你確定政府對此商品是應收稅還是補貼的最少金額（也為整數），才能使商家在這樣一種政府預期的價格上，獲取相對其他價位上的最大總利潤。

總利潤=單位商品利潤*銷量

單位商品利潤=單位商品價格 - 單位商品成本 （- 稅金 or + 補貼）

輸入輸出格式

輸入格式：

?

輸入的第一行為政府對某種商品的預期價，第二行有兩個整數，第一個整數為商品成本，第二個整數為以成本價銷售時的銷售量，以下若干行每行都有兩個整數，第一個為某價位時的單價，第二個為此時的銷量，以一行-1，-1表示所有已知價位及對應的銷量輸入完畢，輸入的最后一行為一個單獨的整數表示在已知的最高單價外每升高一塊錢將減少的銷量。

?

輸出格式：

?

輸出有兩種情況：若在政府預期價上能得到最大總利潤，則輸出一個單獨的整數，數的正負表示是補貼還是收稅，數的大小表示補貼或收稅的金額最小值。若有多解，取絕對值最小的輸出。

如在政府預期價上不能得到最大總利潤，則輸出“NO SOLUTION”。

?

輸入輸出樣例

輸入樣例#1：?復制 31 28 130 30 120 31 110 -1 -1 15 輸出樣例#1：?復制 4

?

參考題解：https://www.luogu.org/problemnew/solution/P1023

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 10001 using namespace std; int i,j,s,t,x,x1,n1,n2,flag,flag1,flag2,a[N],b[N],change; int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } int cmp(int a,int b) {return a>b;} int main() {x=read();a[0]=read(),b[0]=read();while(1){++t;a[t]=read(),b[t]=read();if(a[t]==-1&&b[t]==-1) break; }//--t;sort(a,a+t);sort(b,b+t,cmp);change=read();s=t;for(i=1;i<t;i++)if(a[i]-a[i-1]>1)for(j=a[i-1]+1;j<a[i];j++){a[s]=j;b[s]=b[i-1]-(b[i-1]-b[i])/(a[i]-a[i-1])*(j-a[i-1]);s++;}sort(a,a+s);sort(b,b+s,cmp);for(i=1;i<s;i++)if(a[i]==x)x1=b[i],flag=true;if(!flag) x1=b[s-1]-(x-a[s-1])*change;for(i=0;;i++){flag1=0,flag2=0;n1=(x-a[0]+i)*x1;n2=(x-a[0]-i)*x1;for(j=1;;j++){if(j>=s){b[j]=b[j-1]-change;a[j]=a[j-1]+1;}if(b[j]<=0) break;if(n1<(a[j]-a[0]+i)*b[j]) flag1=1;if(n2<(a[j]-a[0]-i)*b[j]||n2<=0) flag2=1;}if(flag1==0&&flag2==1) break;else if(flag1==1&&flag2==0) break;else if(flag1==0&&flag2==0) break;else if(i==b[0]*10){flag1=-2;break;}}if(flag1==1&&flag2==0) printf("-%d",i);else if(flag1==0&&flag2==1) printf("%d",i);else if(flag1==0&&flag2==0) printf("%d",i);else if(flag1==-2) printf("NO SOLUTION");return 0; }

?

轉載于:https://www.cnblogs.com/z360/p/8228504.html

總結

以上是生活随笔為你收集整理的洛谷——P1023 税收与补贴问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。