poj部分题目答案（四）

1042

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int ans[30][30],f[30],d[30],t[30];
int main()
{
    int h,n;
    cin>>n;
    while(true)
    {
        if(n==0)    break;

        cin>>h;
        h*=12;
        memset(ans,0,sizeof(ans));
        memset(f,0,sizeof(f));
        memset(t,0,sizeof(t));
        memset(d,0,sizeof(d));

        for(int i=1;i<=n;++i)
        {
            scanf("%d",&f[i]);
        }
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&d[i]);
        }
        for(int i=1;i<n;++i)
        {
            scanf("%d",&t[i]);
        }

        int ht,ft[30];
        for(int ed=1;ed<=n;++ed)//枚举从第一个湖开始走
        {
            memset(ft,0,sizeof(ft));
            for(int i=1;i<=ed;++i)
            {
                ft[i]=f[i];
            }//ft作为f的临时记录
            ht=h;//记录剩余时间
            for(int i=1;i<ed;++i)
            {
                ht-=t[i];//先花时间去走路
            }
            //剩余的时间来钓鱼
            int k,emp=1;//emp代表当前的湖
            while(ht>0&&emp<=ed)//时间用完或湖空为止
            {
                k=1;
                for(int j=emp;j<=ed;++j)
                {
                    if(ft[j]>ft[k])
                    {
                        k=j;
                    }
                }//找出最优的湖用ans[池塘编号][0]表示收获量，其余元素表示需要的时间
                ans[ed][0]+=ft[k];//此次收获+ft[k]
                ++ans[ed][k];//记录在k湖花费了1单位时间
                --ht;//时间消耗1单位
                ft[k]-=d[k];//鱼的总量减少
                ft[k]=ft[k]>0?ft[k]:0;
                for(int j=emp;j<=ed;++j)
                {
                    if(ft[j]==0)    ++emp;//若有湖空了，则进入下一个湖
                    else            break;
                }//检查是否ed前的湖都已空
            }
            if(ht>0)    ans[ed][1]+=ht;//若尝试了所有的湖后时间有剩余
        }

        int a=1;
        for(int i=2;i<=n;++i)
        {
            if(ans[i][0]>ans[a][0])    a=i;
        }//找出收益最大的方案

        for(int i=1;i<=n;++i)
        {
            cout<<ans[a][i]*5;//输出所有的池塘所待的时间
            if(i!=n)    cout<<", ";
        }
        cout<<endl;
        cout<<"Number of fish expected: "<<ans[a][0]<<endl;
        
        cin>>n;
        if(n!=0)    cout<<endl;
    }
    return 0;
}

1328

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int n,d;
int x,y;
int num=0,ans,flag;
const int maxn=1005;
typedef double db;
typedef pair<db,db> pdd;
pdd ils[maxn];
bool cmp(pdd a,pdd b){
	if(a.first!=b.first) return a.first<b.first;
	else return a.second>b.second;
}
void solve(){
	if(flag){
		printf("Case %d: -1\n",num);
		//cout<<"Case "<<num<<": -1"<<'\n';
		return;
	}
	sort(ils+1,ils+1+n,cmp);
	db nowl,nowr,nextl,nextr;
	nowl=ils[1].first;
	nowr=ils[1].second;
	ans++;
	for(int i=2;i<=n;i++){
		nextl=ils[i].first;
		nextr=ils[i].second;
		if(nextl>nowr){
			nowl=nextl,nowr=nextr;
			ans++;
		}
		else{
			nowl=max(nowl,nextl);
			nowr=min(nowr,nextr);
		}
	}
	printf("Case %d: %d\n",num,ans);
	//cout<<"Case "<<num<<": "<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	while(cin>>n>>d&&(n||d)){
		num++;
		flag=ans=0;
		for(int i=1;i<=n;i++){
			cin>>x>>y;
			db a,b,c;
			a=1;b=-2*x;c=x*x+y*y-d*d;
			ils[i].first=(-b-sqrt(b*b-4*a*c))/2*a;
			ils[i].second=(-b+sqrt(b*b-4*a*c))/2*a;
			if((b*b-4*a*c)<0||d<=0||y<0) flag=1;
		}
		solve();
	}
	return 0;
}

3040

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
struct coin{
    int value,num;
    int cnt;
    bool operator< (const coin &b) const{
        return value>b.value;
    }
};
const int maxn=25;
coin coins[maxn];

int main(){
    int N,C;
    cin>>N>>C;
    for(int i=0; i<N; i++){
        scanf("%d%d", &coins[i].value, &coins[i].num);
    }
    sort(coins, coins+N);

    LL sum=0;
    bool flag=true;
    while(true){
        int need=C,cnt;
        if(flag){
            for(int i=0; i<N; i++){
                // cnt用来记录当前方案使用对应硬币的数量
                coins[i].cnt=cnt=min(need/coins[i].value, coins[i].num);
                coins[i].num-=cnt;
                need-=cnt*coins[i].value;
            }
            
            int i=N-1;
            for(; i>=0; i--){
                cnt=min((need+coins[i].value-1)/coins[i].value, coins[i].num);
                coins[i].cnt+=cnt;
                coins[i].num-=cnt;
                need-=cnt*coins[i].value;
                
                if(need<=0) break;
            }
        }
        else{ // 贪心加速
            for(int i=0; i<N; i++){
                coins[i].num-=coins[i].cnt;
            }
            need=0;
        }
        
        // 判断当前硬币能不能够再做一遍当前方案
        flag=false;
        for(int i=0; i<N; i++)
            if(coins[i].cnt>coins[i].num){
                flag=true;
                break;
            }
        
        sum++;
        if(need>0) break;
    }
    cout<<sum-1;
    
    return 0;
}

1700

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1005];
int main()
{
    int T;
    int n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);  //从小到大排序
        int time = 0;
        while(n > 3)
        {//两种方案时间比较
            int t = a[n-1]+a[0]+a[1]+a[1]+time;  
            int s = a[n-1]+a[0]+a[n-2]+a[0]+time;
            if(t < s)
                time = t;
            else
                time = s;
            n = n-2;
        }
        if(n == 3)
            time = time + a[0]+a[1]+a[2];
        else if(n ==2)
            time = time + a[1];
        else if(n == 1)
            time = time + a[0];
        printf("%d\n",time);
    }
    return 0;
}

2586

#include <stdio.h>
int main()
{
	const int mode[5] = {2, 4, 6, 9, 12};
	int s, d, k;
	while(scanf("%d%d", &s, &d)!=EOF)
	{
		k = 1;
		while(s*(5-k) - d*k > 0) k++;
		k = s*(12-mode[k-1]) - d*mode[k-1];
		if(k<0) printf("Deficit\n");
		else printf("%d\n", k);
	}
	return 0;
}