http://zqynux.blog.163.com/blog/static/1674995972010622104133878/
by XYZinc @ 2017-03-02 16:42:29
```cpp
#include <stdio.h>
#include <math.h>
#define add(a, b) do{\
goods[count].priece = (a);\
goods[count].number = (b);\
count++;\
}while(0)
#define min(a, b) ((a)<(b)?(a):(b))
#define max(a, b) ((a)>(b)?(a):(b))
struct goods{
int priece;
int number;
}goods[10000];
int count;
int x, number, cost;
void init(void)
{
int i;
int a, b;
int c, d;
int k, f;
scanf("%d", &x);
scanf("%d%d", &a, &b);
cost = a;
x -= cost;
while(scanf("%d%d", &c, &d), (c != -1 || d != -1)){
k = (d - b) / (c - a);
f = d - c * k;
for(i = a; i <= c - 1; i++){
add(i - cost, k * i + f);
}
a = c, b = d;
}
scanf("%d", &k);
for(i = a; (b - (i - a) * k) > 0; i++){
add(i - cost, (b - (i - a) * k));
}
}
int main(void)
{
int i, j;
int a, b, k;
double up = -100000, down = 1000000;
init();
for(i = 0; i < count; i++){
if(goods[i].priece == x){
number = goods[i].number;
break;
}
}
for(i = 0; i < count; i++){
k = 1;
a = goods[i].priece * goods[i].number - number * x;
b = number - goods[i].number;
if(b < 0){
k = -1;
}
if(b != 0){ //排除goods[i].priece == x的情况
if(k == 1){
up = max(up, (double)a / b);
}else{
down = min(down, (double)a / b);
}
}
}
if(up <= down){
if(up > 0){
printf("%d\n", (int)ceil(up));
}else{
down = fabs(down);
printf("%d\n", - (int)ceil(down));
}
}else{
printf("NO SOLUTION\n");
}
return 0;
}
```
by 何加驹 @ 2017-06-21 15:51:20