Sicily 1099 Packing Passengers

2024-01-14 18:10
文章标签 packing sicily 1099 passengers

本文主要是介绍Sicily 1099 Packing Passengers,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Constraints
Time Limit: 1 secs, Memory Limit: 32 MB
Description
PTA, Pack ‘em Tight Airlines is attempting the seemingly impossible—to fly with only full planes and still make a profit. Their strategy is simplicity and efficiency. Their fleet consists of 2 types of equipment (airline lingo for airplanes). Type A aircraft cost costA dollars to operate per flight and can carry passengersA passengers. Type B aircraft cost costB dollars to operate per flight and can carry passengersB passengers.
PTA has been using software that works well for fewer than 100 passengers, but will be far too slow for the number of passengers they expect to have with larger aircraft. PTA wants you to write a program that fills each aircraft to capacity (in keeping with the name Pack 'em Tight) and also minimizes the total cost of operations for that route.
Input
The input file may contain data sets. Each data set begins with a line containing the integer n (1 <= n <= 2,000,000,000) which represents the number of passengers for that route. The second line contains costA and passengersA, and the third line contains costB and passengersB. There will be white space between the pairs of values on each line. Here, costA, passengersA, costB, and passengersB are all nonnegative integers having values less than 2,000,000,001.
After the end of the final data set, there is a line containing “0” (one zero) which should not be processed.
Output
For each data set in the input file, the output file should contain a single line formatted as follows:
Data set : aircraft A, aircraft B
Where is an integer number equal to 1 for the first data set, and incremented by one for each subsequent data set, is the number of airplanes of type A in the optimal solution for the test case, and is the number of airplanes of type B in the optimal solution. The ‘optimal’ solution is a solution that lets PTA carry the number of passengers specified in the input for that data set using only airplanes loaded to their full capacity and that minimizes the cost of operating the required flights. If multiple alternatives exist fitting this description, select the one that uses most airplanes of type A. If no solution exists for PTA to fly the given number of passengers, the out line should be formatted as follows:
Data set : cannot be flown
Sample Input
600
30 20
20 40
550
1 13
2 29
549
1 13
2 29
2000000000
1 2
3 7
599
11 20
22 40
0
Sample Output
Data set 1: 0 aircraft A, 15 aircraft B
Data set 2: 20 aircraft A, 10 aircraft B
Data set 3: 11 aircraft A, 14 aircraft B
Data set 4: 6 aircraft A, 285714284 aircraft B
Data set 5: cannot be flown
这道题的目的是在让每架飞机都满载的情况之下运走所有乘客,并选择花费最少的一个,思路让性价比低的飞机的架数尽可能的少,并满足飞机必须满载的要求,核心代码如下
先考虑numa或numb为0的情况
在这里插入图片描述
然后根据题目的要求及性价比选择飞机
在这里插入图片描述
在这里插入图片描述

#include<iostream>
using namespace std;
int main(){int n;int times=1;while(cin>>n&&n!=0){bool flag=false;int costa,costb;int numa,numb;cin>>costa>>numa>>costb>>numb;if(numa==0){if(n%numb==0){int num=n/numb;cout<<"Data set "<<times++<<": 0 aircraft A, "<<num<<" aircraft B"<<endl;}else{cout<<"Data set "<<times++<<": cannot be flown"<<endl;}continue;}if(numb==0){if(n%numa==0){int num=n/numa;cout<<"Data set "<<times++<<": "<<num<<" aircraft A, "<<"0 aircraft B"<<endl;}else{cout<<"Data set "<<times++<<": cannot be flown"<<endl;}continue;}double pera,perb;pera=(double)costa/(double)numa;perb=(double)costb/(double)numb;if(pera<=perb){int max=n/numb;int a,b;for(int i=0;i<=max;i++){int left=n-i*numb;if(left%numa==0&&left!=0){a=left/numa;b=i;flag=true;break;}if(left==0){a=0;b=max;flag=true;}}if(flag){cout<<"Data set "<<times++<<": "<<a<<" aircraft A, "<<b<<" aircraft B"<<endl;}}else{int max=n/numa;//cout<<max;int a,b;for(int i=0;i<=max;i++){int left=n-i*numa;if(left%numb==0&&left!=0){b=left/numb;a=i;flag=true;break;}if(left==0){b=0;a=max;flag=true;}}if(flag){cout<<"Data set "<<times++<<": "<<a<<" aircraft A, "<<b<<" aircraft B"<<endl;}}if(!flag){cout<<"Data set "<<times++<<": cannot be flown"<<endl;}}
}

这篇关于Sicily 1099 Packing Passengers的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/606054

相关文章

找第K大数(ACdream 1099)

瑶瑶的第K大 Time Limit: 4000/2000MS (Java/Others)  Memory Limit: 256000/128000KB (Java/Others) Submit  Statistic  Next Problem Problem Description 一天,萌萌的妹子--瑶瑶(tsyao)很无聊,就来找你玩。可是你们都不知道玩什么。。。

Address localhost:1099 is already in use:tomcat频繁重启端口占用问题

错误提示 Unable to open debugger port (127.0.0.1:58198): java.net.SocketException "Socket closed" Address localhost:1099 is already in use 端口被占用 报错原因 由于短时间内频繁运行tomcat服务器。 为了避免出现这一错误。可以点击刷新uodate

USACO Section 1.4 Packing Rectangles

题意: 已知4个矩形的l和w  矩形可以旋转和平移  用一块最小面积的新的矩形覆盖4个矩形 求最小的面积  以及新矩形的l和w 思路: 题目已经给出6种摆放方式  按它的方式摆即可 我们要枚举4个矩形是否旋转(只转90度)过  然后枚举每种摆放方式中矩形的编号 代码中的枚举方法是二进制枚举旋转  全排列枚举编号 最后计算所有情况中的答案 第6种摆放方式比较难想  大致思路就是

【数学】 HDU 1099 Lottery

HDU 1099 Lottery 题意没懂, 看了discuss,有人说的,才懂了。。。 #include <stdio.h>#include <iostream>#include <string>#include <cstring>using namespace std;__int64 gcd(__int64 a, __int64 b){if(b == 0) return

sicily 分类

原文出处:http://linguifan2010.blog.163.com/blog/static/1315127442010102131322482/ *************************程序设计题************************* *************************数据结构************************* sicily

uniapp wgt多环境打包与调试插件——uni-packing-wgt

文章目录 背景介绍安装与使用 背景介绍 由于官方的HBuilderX编译器打包wgt每次都要手动的操作有些繁琐,也不支持多环境打包,在开发阶段与原生项目交互调试是极其不方便。而uni-packing-wgt正好可以解决这些问题。 uni-packing-wgt是uniapp跨平台多环境资源打包、调试、发布的插件工具。业内首款开源的wgt多环境打包插件。 主要特性: 支持同

装箱(背包)问题(Packing Problem)

装箱问题也叫背包问题,简单来说,就是把小货物往大箱子里装,要如何才能装得多。个人常见的经历就是“装冰箱”,很有趣的现象就是常常感觉冰箱再也装不下了,但是经过一翻折腾之后又神奇的装下了。   从企业运作角度来看就是尽量让每个容器(仓库、车辆、集装箱、船等)装的尽量多,可以节约企业的费用。通常,装载率85%左右,使用装箱优化方法后,可以达到90~95%左右。海尔做过一个海运装箱的项目,节约了大量运

ACdream 1099 (STL:求数组中第k小的数)

看到群里在聊这个题,就新学这个nth_element()AC了 想了下内部远离应该就是快速排序的partition吧 nth_element(a, a+k, a+n) 求a[0] - a[n-1]范围内第k小的数 代码如下: #include <bits/stdc++.h>#define MAXN 5000010using namespace std;int a[MAXN];in

uva 1099 - Sharing Chocolate(记忆化搜索)

题目链接:uva 1099 - Sharing Chocolate 题目大意:给出一个巧克力,以及它的长和宽,要求判断能否将这个巧克力分成n个指定面积大小的小巧克力。 解题思路:记忆化,d[S][x],表示说集合S,用x = min(r0,c0)的情况能否可行。注意面积要恰好相等才行。 #include <stdio.h>#include <string.h>#in

IDEA:运行 Tomcat 报错 “1099”

1、报错的结果 报错  就很明显啊   localhost:1099 端口号被使用了 2、报错原因 tomcat的端口已经被使用,与运行的起了冲突。强制结束项目,但端口号没有被释放短时间内频繁运行tomcat服务器。 3、解决方法 win + R  输入 cmd  打开命令框     黑窗口输入netstat -aon | findstr 1099,找到占用1099端口的进程ID:PI