SGU - 186 - The Chain (贪心)
2024-10-11 01:01:06
186. The Chain
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
memory limit per test: 4096 KB
input: standard input
output: standard output
output: standard output
Smith has N chains. Each chain is the sequence of successively connected links. The length of each chain is known: the first chain contains L1 links, the second - L2, ..., the last one - LN.
He can make a following series of actions in a minute:
1. to unchain one link
2. to remove or to put into the unchained link some other links of any chain
3. to chain the link
Your task is to determine the minimum time which will take the smith to connect all the chains in one line, i.e. the chain will look like a chain made up of successively connected links.
He can make a following series of actions in a minute:
1. to unchain one link
2. to remove or to put into the unchained link some other links of any chain
3. to chain the link
Your task is to determine the minimum time which will take the smith to connect all the chains in one line, i.e. the chain will look like a chain made up of successively connected links.
Input
The first line contains natural number N<=100. The second line contains L1, L2, ..., LN (1<=Li<=100, for all i = 1..N).
Output
Output the only integer number - the solution to the problem.
Sample test(s)
Input
2 3 4
Output
1
Author: | Michael R. Mirzayanov |
Resource: |
ACM International Collegiate Programming Contest 2003-2004 North-Eastern European Region, Southern Subregion |
Date: | 2003 October, 9 |
思路:好无耻的英语。说的这么拐弯抹角真的好吗?题意应该是这种。先从一个chain上拆下一个link。然后能够连接两个chain,仅仅到全部chain都连起来为止,这里算一分钟。所以先从短链開始拆更省时,贪心....
AC代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int a[105]; int main() {
int n;
while(scanf("%d", &n) != EOF) {
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
} sort(a, a+n); int i = 0, j = n-1, ans = 0;
while(i < j) {
a[i]--;
j--;
if(a[i] == 0) i++;
ans++;
} printf("%d\n", ans);
}
return 0;
}
最新文章
- (八)数据呈现——一图胜千言<;完结>;
- Python 【第十章】 Django路由
- cookie记住密码功能
- 【转】B树、B-树、B+树、B*树
- Linux学习三部曲(之三)
- (转)VS自带工具:dumpbin的使用
- Python安装后在CMD命令行下出现“应用程序无法启动.............”问题
- htm跨域锚点定位
- 系统简单的UIImagePickerController
- dedesms中的导致生成静态页面多出&#65279空白行解决办法
- OPP面向对象的介绍及使用
- 如何用JavaScript制作循环图形
- IOS中 浅谈iOS中MVVM的架构设计与团队协作
- 第一次JVM分析记录:Out of Memory Error (workgroup.cpp:96), pid=6196, tid=139999645685504
- java课程之团队开发冲刺阶段1.2
- 2018-2019-2 20165336《网络对抗技术》Exp0 Kali安装 Week1
- redis hashmap数据结构分析
- django-CRM-项目部署
- [转帖]HTTPS的简单说明
- JAVA练手--String