P1842 [USACO05NOV] 奶牛玩杂技
题目背景
Farmer John 养了 N N N 头牛，她们已经按 1 ∼ N 1\sim N 1∼N 依次编上了号。FJ 所不知道的是，他的所有牛都梦想着从农场逃走，去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳（她们还尝试过把自己装在大炮里发射出去，但可想而知，结果是悲惨的） 。最终，她们决定练习一种最简单的杂技：把所有牛都摞在一起， 比如说， 第一头牛站在第二头的身上， 同时第二头牛又站在第三头牛的身上…最底下的是第 N N N 头牛。
题目描述
每头牛都有自己的体重以及力量，编号为 i i i 的奶牛的体重为 W i W_i Wi，力量为 S i S_i Si。
当某头牛身上站着另一些牛时它就会在一定程度上被压扁，我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛，她的压扁指数等于摞在她上面的所有奶牛的总重（当然不包括她自己）减去它的力量。奶牛们按照一定的顺序摞在一起后， 她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。
你的任务就是帮助奶牛们找出一个摞在一起的顺序，使得总压扁指数最小。
输入格式
第一行一个整数 N N N。
接下来 N N N 行，每行两个整数 W i W_i Wi 和 S i S_i Si。
输出格式
一行一个整数表示最小总压扁指数。
输入输出样例 #1
输入 #1
3
10 3
2 5
3 3
输出 #1
2
说明/提示
对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 5 × 1 0 4 1 \le N \le 5\times 10^4 1≤N≤5×104， 1 ≤ W i ≤ 1 0 4 1 \le W_i \le 10^4 1≤Wi≤104， 1 ≤ S i ≤ 1 0 9 1 \le S_i \le 10^9 1≤Si≤109。
#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
struct node{
int w,s;
bool operator<(node &t){
return w+s < t.w + t.s;
}
}a[N];
int n;
int main(){
cin >> n;
for(int i = 1; i <=n; i++)cin >> a[i].w >> a[i].s;
sort(a+1,a+1+n);
int res = -2e9,t = 0;
for(int i = 1; i <= n; i++){
res = max(res,t - a[i].s);
t += a[i].w;
}
cout << res << endl;
return 0;
}
P1223 排队接水
题目描述
有 n n n 个人在一个水龙头前排队接水，假如每个人接水的时间为 T i T_i Ti，请编程找出这 n n n 个人排队的一种顺序，使得 n n n 个人的平均等待时间最小。
输入格式
第一行为一个整数 n n n。
第二行 n n n 个整数，第 i i i 个整数 T i T_i Ti 表示第 i i i 个人的接水时间 T i T_i Ti。
输出格式
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
输入输出样例 #1
输入 #1
10
56 12 1 99 1000 234 33 55 99 812
输出 #1
3 2 7 8 1 4 9 6 10 5
291.90
说明/提示
1 ≤ n ≤ 1000 1\le n \leq 1000 1≤n≤1000， 1 ≤ t i ≤ 1 0 6 1\le t_i \leq 10^6 1≤ti≤106，不保证 t i t_i ti 不重复。
#include<bits/stdc++.h>
using namespace std;
struct node{
int i,id;
bool operator(node &b){
return t <b.t;
}
}a[1010];
int main(){
int n; cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i].t,a[i].id = i;
}
sort(a+1,a+n+1);
for(int i = 1; i<=n; i++){
cout << a[i].id << " ";
}
puts("");
double tim = 0;
for(int i = 1; i <= n-1; i++){
tim+=a[i].t*(n-i);
printf(".2lf",tim/n);
}
return 0;
}
P1190 [NOIP 2010 普及组] 接水问题
题目描述
学校里有一个水房，水房里一共装有 m m m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1 1 1。
现在有 n n n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 1 1 1 到 n n n 编号， i i i 号同学的接水量为 w i w_i wi。接水开始时， 1 1 1 到 m m m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学 j j j 完成其接水量要求 w j w_j wj 后，下一名排队等候接水的同学 k k k 马上接替 j j j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j j j 同学第 x x x 秒结束时完成接水，则 k k k 同学第 x + 1 x+1 x+1 秒立刻开始接水。若当前接水人数 n ′ n' n′ 不足 m m m，则只有 n ′ n' n′ 个龙头供水，其它 m − n ′ m - n' m−n′ 个龙头关闭。
现在给出 n n n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
输入格式
第一行两个整数 n n n 和 m m m，用一个空格隔开，分别表示接水人数和龙头个数。
第二行 n n n 个整数 w 1 , w 2 , … , w n w_1,w_2,\ldots,w_n w1,w2,…,wn，每两个整数之间用一个空格隔开， w i w_i wi 表示 i i i 号同学的接水量。
输出格式
一个整数，表示接水所需的总时间。
输入输出样例 #1
输入 #1
5 3
4 4 1 2 1
输出 #1
4
输入输出样例 #2
输入 #2
8 4
23 71 87 32 70 93 80 76
输出 #2
163
说明/提示
【输入输出样例 #1 说明】
第 1 1 1 秒， 3 3 3 人接水。第 1 1 1 秒结束时， 1 , 2 , 3 1,2,3 1,2,3 号同学每人的已接水量为 1 , 3 1,3 1,3 号同学接完水， 4 4 4 号同学接替 3 3 3 号同学开始接水。
第 2 2 2 秒， 3 3 3 人接水。第 2 2 2 秒结束时， 1 , 2 1,2 1,2 号同学每人的已接水量为 2 , 4 2,4 2,4 号同学的已接水量为 1 1 1。
第 3 3 3 秒， 3 3 3 人接水。第 3 3 3 秒结束时， 1 , 2 1,2 1,2 号同学每人的已接水量为 3 , 4 3,4 3,4 号同学的已接水量为 2 2 2。 4 4 4 号同学接完水， 5 5 5 号同学接替 4 4 4 号同学开始接水。
第 4 4 4 秒， 3 3 3 人接水。第 4 4 4 秒结束时， 1 , 2 1,2 1,2 号同学每人的已接水量为 4 , 5 4,5 4,5 号同学的已接水量为 1 1 1。 1 , 2 , 5 1,2,5 1,2,5 号同学接完水，即所有人完成接水的总接水时间为 4 4 4 秒。
【数据范围】
1 ≤ n ≤ 10 4 1 \le n \le {10}^4 1≤n≤104， 1 ≤ m ≤ 100 1 \le m \le 100 1≤m≤100， m ≤ n m \le n m≤n；
1 ≤ w i ≤ 100 1 \le w_i \le 100 1≤wi≤100。
NOIP2010 普及组 第二题
#include<bits/stdc++.h>
using namespace std;
int n , m ,w[10005]；
int s[105];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> w[i];
}
for(int i = 1,t; i<=n; i++){
t = 1;
for(int j = 2; j <= m; j++){
if(s[t] > s[j])t = j;
}
s[j] += w[i];
}
int mx = 0;
for(int i = 1; i <= m; i++)mx = max(mx,s[i]);
cout << mx;
return 0;
}
P1209 [USACO1.3] 修理牛棚 Barn Repair
题目描述
在一个月黑风高的暴风雨夜，Farmer John 的牛棚的屋顶、门被吹飞了 好在许多牛正在度假，所以牛棚没有住满。
牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。
自门遗失以后，Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。 Farmer John 想将他购买的木板总长度减到最少。
给出 m , s , c m,s,c m,s,c，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛棚所需木板的最小总长度。
输入格式
一行三个整数
m
,
s
,
c
m,s,c
m,s,c，意义如题目描述。
接下来
c
c
c 行，每行包含一个整数，表示牛所占的牛棚的编号。
输出格式
输出一行一个整数，表示所需木板的最小总长度。
输入输出样例 #1
输入 #1
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43
输出 #1
25
说明/提示
【数据范围】
对于
100
%
100\%
100% 的数据，
1
≤
m
≤
50
1\le m \le 50
1≤m≤50，
1
≤
c
≤
s
≤
200
1\le c \le s \le 200
1≤c≤s≤200。
USACO Training Section 1.3
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int m,c,s,ans;
int a[N],d[N];
int main(){
cin >> m >> s >> c;
for(int i = 1; i <= c; i++){
cin >> a[i];
}
sort(a+1,a+c+1);
for(int i = 2; i <= c; i++)d[i-1] = a[i]-a[i-1]-1;
sort(d+1,d+c);
ans = c;
if(m < c){
for(int i = 1; i <= c - m; i++)ans += d[i];
}
cout << ans;
return 0;
}
P1843 奶牛晒衣服
题目背景
熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。
题目描述
一件衣服在自然条件下用一秒的时间可以晒干 a a a 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 b b b 点湿度（一秒晒干 a + b a+b a+b 湿度），但在同一时间内只能烘一件衣服。现在有 n n n 件衣服，第 i i i 衣服的湿度为 w i w_i wi（保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 0 0 0 为干 ）。
输入格式
第一行三个整数，分别为
n
,
a
,
b
n,a,b
n,a,b。
接下来
2
2
2 到
n
+
1
n+1
n+1 行，第
i
i
i 行输入
w
i
w_i
wi。
输出格式
一行，弄干所有衣服的最少时间。
输入输出样例 #1
输入 #1
3 2 1
1
2
3
输出 #1
1
说明/提示
样例解释
让机器烘第三件衣服即可一秒完成。
数据范围
1 ≤ w i , a , b , n ≤ 5 × 1 0 5 1 \le w_i,a,b,n \le 5 \times 10^5 1≤wi,a,b,n≤5×105
#include<bits/stdc++.h>
using namespace std;
priority_queue<int>q;
int n,a,b;
int tim , mx;
int main(){
cin >> n >> a >> b;
for(int i = 1;i <= n; i++){
int x;
cin >> x;
q.push(x);
}
mx = q.top();
q.pop();
while(mx > tim*a){
tim++;
mx -= b;
q.push(mx);
mx = q.top();
q.pop();
}
cout << tim;
return 0;
}
P1803 凌乱的yyy / 线段覆盖
题目背景
Python 用户可以尝试使用 pypy3 提交试题。
快 noip 了，yyy 很紧张！
题目描述
现在各大 oj 上有 n n n 个比赛，每个比赛的开始、结束的时间点是知道的。
yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。
所以，他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 2 2 2 个及以上的比赛。
输入格式
第一行是一个整数 n n n，接下来 n n n 行每行是 2 2 2 个整数 a i , b i ( a i < b i ) a_{i},b_{i}\ (a_{i}<b_{i}) ai,bi (ai<bi)，表示比赛开始、结束的时间。
输出格式
一个整数最多参加的比赛数目。
输入输出样例 #1
输入 #1
3
0 2
2 4
1 3
输出 #1
2
说明/提示
- 对于 20 % 20\% 20% 的数据， n ≤ 10 n \le 10 n≤10；
- 对于 50 % 50\% 50% 的数据， n ≤ 1 0 3 n \le 10^3 n≤103；
- 对于 70 % 70\% 70% 的数据， n ≤ 1 0 5 n \le 10^{5} n≤105；
- 对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1 0 6 1\le n \le 10^{6} 1≤n≤106， 0 ≤ a i < b i ≤ 1 0 6 0 \le a_{i} < b_{i} \le 10^6 0≤ai<bi≤106。
#include<bits/stdc++.h>
using namespace std;
struct line{
int l ,r;
bool operator<(line &b){
return r<b.r;
}
}a[1000005];
int n , last ,cnt;
int main(){
cin >> n;
for(int i = 1;i <= n; i++){
cin >> a[i].l >> a[i].r;
}
sort(a+1,a+n+1);
for(int i = 1; i <= n; i++){
if(last <= a[i].l){
last =a[i].r;
cnt++;
}
}
cout << cnt;
return 0;
}
P1031 [NOIP 2002 提高组] 均分纸牌
题目描述
有 N N N 堆纸牌，编号分别为 1 , 2 , … , N 1,2,\ldots,N 1,2,…,N。每堆上有若干张，但纸牌总数必为 N N N 的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 1 1 1 堆上取的纸牌，只能移到编号为 2 2 2 的堆上；在编号为 N N N 的堆上取的纸牌，只能移到编号为 N − 1 N-1 N−1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 N = 4 N=4 N=4 时， 4 4 4 堆纸牌数分别为 9 , 8 , 17 , 6 9,8,17,6 9,8,17,6。
移动 3 3 3 次可达到目的：
- 从第三堆取 4 4 4 张牌放到第四堆，此时每堆纸牌数分别为 9 , 8 , 13 , 10 9,8,13,10 9,8,13,10。
- 从第三堆取 3 3 3 张牌放到第二堆，此时每堆纸牌数分别为 9 , 11 , 10 , 10 9,11,10,10 9,11,10,10。
- 从第二堆取 1 1 1 张牌放到第一堆，此时每堆纸牌数分别为 10 , 10 , 10 , 10 10,10,10,10 10,10,10,10。
输入格式
第一行共一个整数
N
N
N，表示纸牌堆数。
第二行共
N
N
N 个整数
A
1
,
A
2
,
…
,
A
N
A_1,A_2,\ldots,A_N
A1,A2,…,AN，表示每堆纸牌初始时的纸牌数。
输出格式
共一行，即所有堆均达到相等时的最少移动次数。
输入输出样例 #1
输入 #1
4
9 8 17 6
输出 #1
3
说明/提示
对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 100 1 \le N \le 100 1≤N≤100， 1 ≤ A i ≤ 10000 1 \le A_i \le 10000 1≤Ai≤10000。
【题目来源】
NOIP 2002 提高组第一题
#include<bits/stdc++.h>
using namespace std;
int n,a[101],avg,cnt;
int main(){
cin >> n;
for(int i = 1; i<=n;i++){
cin >> a[i];
avg+=a[i];
}
avg /= n;
for(int i = 1; i<=n;i++){
if(a[i] - avg){
a[i+1]+=a[i] - avg;
cnt++;
}
}
cout << cnt;
return 0;
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
