2. 【NOIP2018】小猪购物

一只小猪要买N件物品(N不超过1000)。它要买的所有物品在两家商店里都有卖。第i件物品在第一家商店的价格是a[i],在第二家商店的价格是b[i],两个价格都不小于0且不超过10000。如果在第一家商店买的物品的总额不少于50000,那么在第一家店买的物品都可以95折(价格变为原来的0.95倍)。求小猪买所有物品所需最少的总额。

补全程序：

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
const int Inf=1000000000;
const int threshold=50000;
const int maxn=1000;
int n,a[maxn],b[maxn];
bool put_a[maxn];
int total_a,total_b;
double ans;
int f[threshold];
int main() {
    scanf("%d",&n);
    total_a=total_b=0;
    for (int i=0;i<n;++i) {
        scanf("%d%d",a+i,b+i);
        if (a[i]<=b[i])total_a+=a[i];
        else total_b+=b[i];
    }
    ans=total_a+total_b;
    total_a=total_b=0;
    for (int i=0;i<n;++i) {
        if ( ① ) {
            put_a[i]=true;
            total_a+=a[i];
        } else {
            put_a[i]=false;
            total_b+=b[i];
        }
    }
    if ( ② ) {
        printf("%.2f",total_a*0.95+total_b);
        return 0;
    }
    f[0]=0;
    for (int i=1;i<threshold;++i)
        f[i]=Inf;
    int total_b_prefix=0;
    for (int i=0;i<n;++i)
        if (!put_a[i]) {
            total_b_prefix+=b[i];
            for (int j=threshold-1;j>=0;--j) {
                if ( ③ >=threshold&&f[j]!=Inf)
                    ans=min(ans,(total_a+j+a[i])*0.95+ ④ );
                f[j]=min(f[j]+b[i],j>=a[i]? ⑤ :Inf);
            }
        }
    printf("%.2f",ans);
    return 0;
}

选择题：

1. ①处应填（ ）
   {{ select(1) }}

• a[i]<=b[i]
• a[i]<b[i]
• a[i]*0.95<=b[i]
• a[i]*0.95<b[i]

2. ②处应填（ ）
   {{ select(2) }}

• total_a>=threshold
• total_a>=total_b
• total_b>=threshold
• total_a<total_b

3. ③处应填（ ）
   {{ select(3) }}

• j+a[i]
• total_b-a[i]
• total_a+j+a[i]
• total_b-total_b_prefix

4. ④处应填（ ）
   {{ select(4) }}

• total_b-total_b_prefix
• f[j]+total_a-total_b
• total_a-total_b_prefix
• f[j]+total_b-total_b_prefix

5. ⑤处应填（ ）
   {{ select(5) }}

• f[j-a[i]]+b[i]
• f[j-b[i]]+a[i]
• f[j-a[i]]
• f[j-b[i]]