Codeforces Round #311 (Div. 2)

Codeforces Round #311 (Div. 2)

我只想說還好我沒有放棄，還好我堅持下來了。

終於變成藍名了，也許這對很多人來說並不算什麼，但是對於一個打了這麼多場才好不容易加分的人來說，我真的有點激動。

心髒的難受也許有點是因為晚上做題時太激動了，看別人過得那麼快自己也緊張了。

後來看到有很多大神給我的建議是，初學者，手速並不是唯一重要的關鍵，掌握算法，一步步系統的完善它才是最重要的。

所以這一回也沒有太緊張，也沒有做一題看一下排名。

然後竟然第一次進了前1000，rating一下子加了220多。

希望這是一個好的開端，我還想繼續下去，變得更強大！

 

 

題解：（因為C題我不會，所以把它寫在了最前面）

 

C. Arthur and Table time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Arthur has bought a beautiful big table into his new flat. When he came home, Arthur noticed that the new table is unstable.

In total the table Arthur bought has n legs, the length of the i-th leg is li.

Arthur decided to make the table stable and remove some legs. For each of them Arthur determined number di — the amount of energy that he spends to remove the i-th leg.

A table with k legs is assumed to be stable if there are more than half legs of the maximum length. For example, to make a table with 5legs stable, you need to make sure it has at least three (out of these five) legs of the maximum length. Also, a table with one leg is always stable and a table with two legs is stable if and only if they have the same lengths.

Your task is to help Arthur and count the minimum number of energy units Arthur should spend on making the table stable.

Input

The first line of the input contains integer n (1 ≤ n ≤ 105) — the initial number of legs in the table Arthur bought.

The second line of the input contains a sequence of n integers li (1 ≤ li ≤ 105), where li is equal to the length of the i-th leg of the table.

The third line of the input contains a sequence of n integers di (1 ≤ di ≤ 200), where di is the number of energy units that Arthur spends on removing the i-th leg off the table.

Output

Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.

Sample test(s) input

2
1 5
3 2

output

2

input

3
2 4 4
1 1 1

output

0

input

6
2 2 1 1 3 3
4 3 5 5 2 1

output

8

 

題意：

xx人他買了一個不是腳的長度長短不一的桌子，它的桌子有n個腳，然後每個腳的長度分別為l[i]。

每次移動掉第i個腳所花費的力氣為d[i]。

要使桌子滿足穩定的條件為：

1）它是一只腳的，那麼它肯定是穩的

2）它是2只腳的，那麼如果兩條腿長度都相同的話，那麼就說明它是穩的

3）它是k只腳的，那麼當腳的長度等於現在桌子中所含的最大長度的數量大於k/2時，則說明它也是穩的

然後要你求出使得桌子變得穩定的它所要付出的最少的力氣。

題解：

這道題我是看別人代碼，然後理解後才打出來的，不得不說別人的腦回路還真是復雜，都能寫出這麼復雜的代碼，而我現在還只在刷刷水題，（太弱了。。。

我就大概講一下核心的思路，其余的都在代碼中注釋的比較詳細了：

 

int ans=inf;
    for(itr=mp.begin();itr!=mp.end();itr++){	//枚舉所出現過的長度 
        int l=(*itr).first;		//l中存的是長度 
        int num=(*itr).second;	//num中存的是出現過的次數 
        int power=s[l];		//power中存的是這個長度所需要的力量數 
        int all=num;		//all中暫時儲存了出現過的次數 
        for(int i=200;i>=1;i--){		//對力量進行暴力枚舉 
            int nn=lower_bound(G[i].begin(),G[i].end(),l)-G[i].begin();	//這裡是為了找到小於等於l的數有幾個 
            all+=nn;
            power+=nn*i;
            if(all>=num*2){
                power-=i*(all-num*2+1);
                break;
            }
        }
        ans=min(ans,sum-power);
    }

首先這裡的目的是為了求出所需要的最小的力量度。那麼我們講一下大概的思路：

 

我們的想法是，假設每次l都是最大的長度，然後我們在再滿足題目中條件的情況下去求力量數。

這裡我們采用了暴力和貪心的想法，我們 對力量進行枚舉，我們要盡可能的先貪心的選取較大的力量（也就是說我們選進去的腿是不用被拆掉的）。

然後這裡可以用二分求出在當前力量下小於等於l長度的有多少個。

當滿足all>=num*2時，說明我們已經選多了，所以我們要減去一些腿，那麼減去哪些呢？（和上面一樣，也是貪心的減去當前力量下的那些桌子腿，因為它們所消耗的力量比較少。。。

因為我們這裡求的是不需要減去的木棍，所以我們要求的是力量的最大值，所以題目要求的力量的最小值就是sum-power了，對吧。。

唔。。。這裡還用了vector，還有迭代器，總之STL用的巧那自然是十分好的。。

 

#include
#include
#include
#include
#include

 

 

 

A. Ilya and Diplomas time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Soon a school Olympiad in Informatics will be held in Berland, n schoolchildren will participate there.

At a meeting of the jury of the Olympiad it was decided that each of the n participants, depending on the results, will get a diploma of the first, second or third degree. Thus, each student will receive exactly one diploma.

They also decided that there must be given at least min1 and at most max1 diplomas of the first degree, at least min2 and at mostmax2 diplomas of the second degree, and at least min3 and at most max3 diplomas of the third degree.

After some discussion it was decided to choose from all the options of distributing diplomas satisfying these limitations the one that maximizes the number of participants who receive diplomas of the first degree. Of all these options they select the one which maximizes the number of the participants who receive diplomas of the second degree. If there are multiple of these options, they select the option that maximizes the number of diplomas of the third degree.

Choosing the best option of distributing certificates was entrusted to Ilya, one of the best programmers of Berland. However, he found more important things to do, so it is your task now to choose the best option of distributing of diplomas, based on the described limitations.

It is guaranteed that the described limitations are such that there is a way to choose such an option of distributing diplomas that all nparticipants of the Olympiad will receive a diploma of some degree.

Input

The first line of the input contains a single integer n (3 ≤ n ≤ 3·106) — the number of schoolchildren who will participate in the Olympiad.

The next line of the input contains two integers min1 and max1 (1 ≤ min1 ≤ max1 ≤ 106) — the minimum and maximum limits on the number of diplomas of the first degree that can be distributed.

The third line of the input contains two integers min2 and max2 (1 ≤ min2 ≤ max2 ≤ 106) — the minimum and maximum limits on the number of diplomas of the second degree that can be distributed.

The next line of the input contains two integers min3 and max3 (1 ≤ min3 ≤ max3 ≤ 106) — the minimum and maximum limits on the number of diplomas of the third degree that can be distributed.

It is guaranteed that min1 + min2 + min3 ≤ n ≤ max1 + max2 + max3.

Output

In the first line of the output print three numbers, showing how many diplomas of the first, second and third degree will be given to students in the optimal variant of distributing diplomas.

The optimal variant of distributing diplomas is the one that maximizes the number of students who receive diplomas of the first degree. Of all the suitable options, the best one is the one which maximizes the number of participants who receive diplomas of the second degree. If there are several of these options, the best one is the one that maximizes the number of diplomas of the third degree.

Sample test(s) input

6
1 5
2 6
3 7

output

1 2 3 

input

10
1 2
1 3
1 5

output

2 3 5 

input

6
1 3
2 2
2 2

output

2 2 2 

題目的大致意思是：

 

現在有三種層次的獎狀，然後要滿足每一種獎狀都必須含有它的min值（同時也要<=max值），也就是說每個獎狀都必須有人獲獎。

想法：

暴力分類就好

 

#include
#include
#include
#include
#include

 

B. Pasha and Tea time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Pasha decided to invite his friends to a tea party. For that occasion, he has a large teapot with the capacity of w milliliters and 2n tea cups, each cup is for one of Pasha's friends. The i-th cup can hold at most ai milliliters of water.

It turned out that among Pasha's friends there are exactly n boys and exactly n girls and all of them are going to come to the tea party. To please everyone, Pasha decided to pour the water for the tea as follows:

• Pasha can boil the teapot exactly once by pouring there at most w milliliters of water;
• Pasha pours the same amount of water to each girl;
• Pasha pours the same amount of water to each boy;
• if each girl gets x milliliters of water, then each boy gets 2x milliliters of water.

  In the other words, each boy should get two times more water than each girl does.

  Pasha is very kind and polite, so he wants to maximize the total amount of the water that he pours to his friends. Your task is to help him and determine the optimum distribution of cups between Pasha's friends.

  Input

  The first line of the input contains two integers, n and w (1 ≤ n ≤ 105, 1 ≤ w ≤ 109) — the number of Pasha's friends that are boys (equal to the number of Pasha's friends that are girls) and the capacity of Pasha's teapot in milliliters.

  The second line of the input contains the sequence of integers ai (1 ≤ ai ≤ 109, 1 ≤ i ≤ 2n) — the capacities of Pasha's tea cups in milliliters.

  Output

  Print a single real number — the maximum total amount of water in milliliters that Pasha can pour to his friends without violating the given conditions. Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 6.

  Sample test(s) input

  2 4
  1 1 1 1
  

  output

  3

  input

  3 18
  4 4 4 2 2 2
  

  output

  18

  input

  1 5
  2 3
  

  output

  4.5

  題意:

   

  xx有一個容量為w升的水壺（他最多只有w升水，因為只能煮一次水，題中說的），然後總共有2n個人來參加他的party。

  xx倒水有如下規則：

  1）女孩子中所倒的水量是相同的

  2）男孩子中所到的水量也是相同的

  3）男孩子的獲得水量是女孩子的2倍

  然後輸出一個實數，問你在滿足上面的條件下，這2n個人他們所能獲得的最多的水量是多少

  題解：

  其實就是列簡單的方程，然後求出約束條件就好（水題一枚~

  哦，對了，最後好多人說都卡了精度，那麼最後輸出.7lf就好

   

  #include
  #include
  #include
  #include
  #include