Codeforces Round #249 (Div. 2) (ABCD题解) - c++编程基础

A. Queue on Bus Stop time limit per test：1 second memory limit per test：256 megabytes

It's that time of the year when the Russians flood their countryside summer cottages (dachas) and the bus stop has a lot of people. People rarely go to the dacha on their own, it's usually a group, so the people stand in queue by groups.

The bus stop queue has n groups of people. The i-th group from the beginning has a_i people. Every 30 minutes an empty bus arrives at the bus stop, it can carry at most m people. Naturally, the people from the first group enter the bus first. Then go the people from the second group and so on. Note that the order of groups in the queue never changes. Moreover, if some group cannot fit all of its members into the current bus, it waits for the next bus together with other groups standing after it in the queue.

Your task is to determine how many buses is needed to transport all n groups to the dacha countryside.

Input

The first line contains two integers n and m (1?≤?n,?m?≤?100). The next line contains n integers: a₁,?a₂,?...,?a_n (1?≤?a_i?≤?m).

Output

Print a single integer — the number of buses that is needed to transport all n groups to the dacha countryside.

Sample test(s) Input

4 3
2 3 2 1

Output

Input

3 4
1 2 1

Output

题目大意：一共n个站台，每个站台一开始有ai个人，一辆车一次最多载m个人，如果当前这辆车不能装下当前站的所有人，则当前站的人都不上车而等下一辆，问搭载所有的人需要几辆车

题目分析：照着题意模拟即可

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int a[105]; int main() { int n, m; scanf(%d %d, &n, &m); for(int i = 0; i < n; i++) scanf(%d, &a[i]); int ans = 1; int now = m; for(int i = 0; i < n;) { if(a[i] <= now) { now -= a[i]; i ++; } else { now = m; ans ++; } } printf(%d , ans); }

B. Pasha Maximizes time limit per test：1 second memory limit per test：256 megabytes

Pasha has a positive integer a without leading zeroes. Today he decided that the number is too small and he should make it larger. Unfortunately, the only operation Pasha can do is to swap two adjacent decimal digits of the integer.

Help Pasha count the maximum number he can get if he has the time to make at most k swaps.

Input

The single line contains two integers a and k (1?≤?a?≤?10¹⁸; 0?≤?k?≤?100).

Output

Print the maximum number that Pasha can get if he makes at most k swaps.

Sample test(s) Input

1990 1

Output

Input

300 0

Output

Input

1034 2

Output

Input

9090000078001234 6

Output

9907000008001234

题目大意：给一个数a，每次只能交换相邻两个数，最多交换k次，求交换后的最大数字

题目分析：贪心问题，显然大数字往前放的贪心策略是错的，正确的应该是尽量让高位的数字大，从最高位开始向低位找，先找到k步之内的最大数，如果k步之内的最大数不是当前位置的数，那么把最大数交换到当前为止，没交换一次，k减1

#include 
  
   
#include 
   
     #include 
    
      using namespace std; char s[20]; int k; int main() { scanf(%s %d, s, &k); int len = strlen(s); int now; for(int i = 0; i < len; i++) { now = i; for(int j = i + 1; j <= i + k && j < len; j++) if(s[j] > s[now]) now = j; if(now != i) { for(int j = now; j > i; j--) { swap(s[j], s[j - 1]); k --; } } } printf(%s , s); }

C. Cardiogram time limit per test：1 second memory limit per test：256 megabytes

In this problem, your task is to use ASCII graphics to paint a cardiogram.

A cardiogram is a polyline with the following corners:

$\$

That is, a cardiogram is fully defined by a sequence of positive integers a₁,?a₂,?...,?a_n.

Your task is to paint a cardiogram by given sequence a_i.

Input

The first line contains integer n (2?≤?n?≤?1000). The next line contains the sequence of integers a₁,?a₂,?...,?a_n (1?≤?a_i?≤?1000). It is guaranteed that the sum of all a_i doesn't exceed 1000.

Output

Print max |y_i?-?y_j| lines (where y_k is the y coordinate of the k-th point of the polyline), in each line print $\$ characters. Each character must equal either ??/?? (slash), ? ? (backslash), ? ? (space). The printed image must be the image of the given polyline. Please study the tes

Codeforces Round #249 (Div. 2) (ABCD题解)(一)