USACO Jan08 Bronze 化裝晚會 costume 解題報告

Title: 化装晚会【題目連結】

Input: costume.in

Output: costume.out

Time Limit: 1000 ms

Memory Limit: 16 MB

Level: ★☆

萬聖節又到了！Farmer John打算帶他的奶牛去參加一個化裝晚會，但是，FJ只做了一套能容 下兩頭總長不超過S(1 <= S <= 1,000,000)的牛的恐怖服裝。FJ養了N(2 <= N <= 20,000)頭按1..N順序編號的奶牛，編號為i的奶牛的長度為L_i(1 <= L_i <= 1,000,000)。如果兩頭奶牛的總長度不超過S，那麼她們就能穿下這套服裝。

FJ想知道，如果他想選擇兩頭不同的奶牛來穿這套衣服，一共有多少種滿足條件的方案。

程序名: costume

 

輸入格式:

• 第1行: 2個用空格隔開的整數：N 和 S

• 第2..N+1行: 第i+1為1個整數：L_i

輸入樣例 (costume.in):

4 6

3

5

2

1

輸出格式:

• 第1行: 輸出1個整數，表示FJ可選擇的所有方案數。注意奶牛順序不同的兩種方案是被視為相同的

輸出樣例 (costume.out):

4

輸出說明:

4種選擇分別為：奶牛1和奶牛3；奶牛1和奶牛4；奶牛2和奶牛4；奶牛3和奶牛4。

【分析】

很明顯，這是二分答案。先為奶牛們排一下序，枚舉每頭奶牛，每次計算出與這隻奶牛同穿恐怖服裝的另一頭奶牛的身長的最大值，然後二分查找這個身長的位置，得到有幾頭奶牛的身長小於這個最大值，不要忘記有可能需要把那個數量減去1（因為這頭奶牛不可能和它本身穿一套服裝），最後把總和除以二即可。

【我的代碼】
裸代碼RawCode

C++语言: Codee#25391

01 /*
02 *Problem: USACO Jan08 Bronze costume
03 *Author: Yeefan-Zhu
04 *GTalk: zyfworks@gmail.com
05 *Website: http://blog.yeefanblog.tk/
06 */
07 #include <cstdio>
08 #include <algorithm>
09 #include <cstdlib>
10 #include <iostream>
11 #define min(a,b) a>b?b:a
12 using namespace std;
13 const int MAXN=20002;
14 int Len[MAXN];
15 int N,S;
16 int Ans=0;
17 int MaxL=0,MinL=0x7fffffff;
18
19 void init()
20 {
21     scanf("%d %d\n",&N,&S);
22     for (int i=1;i<=N;i++)
23     {
24         scanf("%d\n",&Len[i]);
25         MinL=min(MinL,Len[i]);
26     }
27     /*Sort of STL, [container.begin(),container.end)*/
28     sort(Len+1,Len+N+1);
29     Len[0]=Len[1]-1;
30     Len[N+1]=Len[N]+1;
31 }
32
33 int BS(int X)
34 {
35     int l=0,r=N+1,mid;
36     while(l+1!=r)
37     {
38         mid=(l+r)/2;
39         if(Len[mid]<=X)
40             l=mid;
41         else
42             r=mid;
43     }
44     int a=Len[l];
45     int b=Len[r];
46     if(a<=X<b)
47         return l;
48     if(X>=b)
49         return r;
50     return 1;
51 }
52
53 void solve()
54 {
55     for(int i=1;i<=N;i++)
56     {
57         if(Len[i]+MinL>S)
58             break;
59         int Temp=S-Len[i];
60         int Res=BS(Temp);
61         Ans+=Res;
62         if(i<=Res)
63             Ans--;
64     }
65     Ans/=2;
66     printf("%d\n",Ans);
67 }
68
69 int main()
70 {
71     freopen("costume.in","r",stdin);
72     freopen("costume.out","w",stdout);
73     init();
74     solve();
75     return 0;
76 }