Jessica‘s a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.

A very hard-working boy had manually indexed for her each page of Jessica‘s text-book with what idea each page is about and thus made a big progress for his courtship. Here you come in to save your skin: given the index, help Jessica decide which contiguous part she should read. For convenience, each idea has been coded with an ID, which is a non-negative integer.

The first line of input is an integer P (1 ≤ P ≤ 1000000), which is the number of pages of Jessica‘s text-book. The second line contains P non-negative integers describing what idea each page is about. The first integer is what the first page is about, the second integer is what the second page is about, and so on. You may assume all integers that appear can fit well in the signed 32-bit integer type.

Output one line: the number of pages of the shortest contiguous part of the book which contains all ideals covered in the book.

5
1 8 8 8 1

2

贪心，先让l和r等于1，然后r++，在[l,r]区间内，如果全部包括了，就从a[l]开始便利只要a[l]出现次数大于1就l++。每次满足保存一个最新值。

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 #include <map>
 6 #include <set>
 7 #define ll long long
 8 using namespace std;
 9 const int MAX = 1000010;
10 int a[MAX];
11 map<int,int> mp;
12 set<int> st;
13 int main() {
14     int p;
15     while(scanf("%d",&p) !=EOF) {
16         for(int i = 1; i <= p; i ++) {
17             scanf("%d",&a[i]);
18             st.insert(a[i]);
19         }
20         int k = st.size();
21         st.clear();
22         int l = 1, r = 1, minn = MAX*10;
23         while(r <= p) {
24             st.insert(a[r]);
25             mp[a[r]] ++;
26             if(st.size() == k) {
27                 while(mp[a[l]] >= 2) {
28                     mp[a[l]]--;l++;
29                 }
30                 if(r-l+1 < minn) minn = r-l+1;
31             }
32             r++;
33         }
34         printf("%d\n",minn);
35         st.clear();
36         mp.clear();
37         memset(a,0,sizeof(a));
38     }
39     return 0;
40 }

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

0.649

英语渣渣的我看了大半个小时才看懂。用贪心来做，取每个设备的宽带的最大值，在这些最大值的宽带里取最小的那个当成总宽带，然后遍历全部，让价格加上每个设备的宽带大于总宽带的最小价格。

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 #include <vector>
 6 #define ll long long
 7 using namespace std;
 8 const double ef = 1e-9;
 9 const int MAX = 11000;
10 vector<pair<double,double> >vs[MAX];
11 int main() {
12     int t, n, m;
13     ios::sync_with_stdio(false);
14     cin>>t;
15     while(t--) {
16         cin>>n;
17         int b = 100000;
18         for(int i = 1; i <= n; i ++) {
19             cin >> m;
20             int MM = -1;
21             for(int j = 1; j <= m; j ++) {
22                 double x, y;
23                 cin >> x >> y;
24                 if(x > MM) MM = x;
25                 vs[i].push_back(make_pair(x,y));
26             }
27             if(MM < b) b = MM;
28         }
29         double p = 0.0;
30         for(int i = 1; i <= n; i ++) {
31             double pp = 100000;
32             for(int j = 0; j < vs[i].size(); j ++) {
33                 if(vs[i][j].first >= b){
34                     if(pp > vs[i][j].second) pp = vs[i][j].second;
35                 }
36             }
37             // cout << pp << endl;
38             p += pp;
39         }
40         printf("%.3f\n",b/p);
41         //cout << b<< ‘ ‘ << p << endl;
42         for(int i = 1; i <= n; i ++) vs[i].clear();
43     }
44     return 0;
45 }

* Line 1: Three space-separated integers: N, P, and K
* Lines 2..P+1: Line i+1 contains the three space-separated integers: A_i, B_i, and L_i

* Line 1: A single integer, the minimum amount Farmer John can pay. If it is impossible to connect the farm to the phone company, print -1.

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

4


英语好渣，比赛时一直没看懂题意，赛后才知道是求每个方案中总长度最大的最小数。
比如第一组数据走1->2->5  分别是5 9k是1 ，9去掉，答案就是5 走1->3->2->5 分别是4 3 9 ，  9去掉答案是4,4比前面的5小，所以最终答案是4.
做法是dijkstra+二分来做。其实就是求最小的m使得从1到n的路径中比m大的数要小于等于k。
用数组的dijkstra会超时，这时就需要用优先队列来做了，因为数组的复杂度是：O（|V|^2）,优先队列的是O(|E|log|V|)。

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 #include <queue>
 6 #define INF 0x3f3f3f3f
 7 #define ll long long
 8 using namespace std;
 9 const int MAX = 1010;
10 struct Nod {
11     int to, cost;
12 };
13 typedef pair<int,int> P;
14 int n,p,k;
15 vector<Nod> G[MAX];
16 int d[MAX];
17 int dij(int s, int x) {
18     priority_queue<P, vector<P>, greater<P> > que;
19     memset(d,0x3f,sizeof(d));
20     d[s] = 0;
21     que.push(P(0,s));
22     while(!que.empty()) {
23         P p = que.top(); que.pop();
24         int v = p.second;
25         if(d[v] < p.first) continue;
26         for(int i = 0; i < G[v].size(); i ++) {
27             Nod e = G[v][i];
28             int dd = d[v] + (e.cost > x ? 1 : 0);
29             if(d[e.to] > dd) {
30                 d[e.to] = dd;
31                 que.push(P(d[e.to],e.to));
32             }
33         }
34     }
35     return d[n-1];
36 }
37 int main() {
38     //ios::sync_with_stdio(false);
39     while(cin>>n>>p>>k) {
40         for(int i = 1; i <= p; i ++) {
41             int u, v, w;
42             cin >> u >> v >> w;
43             --u;--v;
44             G[u].push_back((Nod){v,w});
45             G[v].push_back((Nod){u,w});
46         }
47         int l = 0, r = 1000010, cnt = -1;
48         while(l <= r) {
49             int m = (l+r) >> 1;
50             int ans = dij(0,m);
51             // printf("%d  %d \n",m,ans);
52             if(ans <= k){
53                 cnt = m;r = m-1;
54             }else l = m+1;
55         }
56         printf("%d\n",cnt);
57     }
58     return 0;
59 }