EducationalCodeforcesRound62(Div. 2)(A-D题解)

http://codeforces.com/contest/1140/problem/A

题意：一个人看一本解谜书，第 i 个谜题的答案在第 ai 页，他会从头一页一页地翻书，如果今天他看过的所有谜题的答案页他都看过了，那么今天就不看了，否则就要一直往下翻。求解这本书多长时间看完。

思路：模拟即可，不断更新今天看过谜题的答案的最大页码。（这破题也能WA，真的是菜。。。）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int a[10005];
 5 int main()
 6 {
 7     int n;
 8     cin >> n;
 9     for(int i = 1;i <= n;i ++){
10         cin >> a[i];
11     }
12     int ans = 0;
13     int now = 1;
14     while(now <= n){
15         int maxx = a[now];
16         while(now != maxx){
17             now ++;
18             maxx = max(a[now],maxx);
19         }
20         now ++;
21         ans ++;
22     }
23     cout << ans << endl;
24 
25     return 0;
26 }

http://codeforces.com/contest/1140/problem/B

题意：给一个只含有 '<' 和 '>' 的字符串，如果你经过若干操作能把它的长度变成 1，那么这个串就是好串。

　　　操作包含两个：1、随便拿出一个 '<' ，然后删除在它左边的所有字符，不包括它本身。

　　　　　　　　　　2、随便拿出一个 '>' ，然后删除在它右边的所有字符，不包括它本身。

　　　你现在可以直接不通过操作删除任意个字符，问你在最少删除多少个字符后，这个串变成好串。

思路：挺坑的一道题，一看是看错问题以为是括号匹配，WA了之后就没思路了。但是想了一会发现，只要从左找第一个右括号，并且从右找到第一个左括号，看看谁先出现就行了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 char a[10005];
 5 int main()
 6 {
 7     int T;
 8     cin >> T;
 9     while(T --){
10         int n;cin >> n;
11         scanf("%s",a);
12         for(int i = 0;i < n;i ++){
13             if(a[i] == '>'){cout << i << endl;break;}
14             if(a[n - i - 1] == '<'){cout << i << endl;break;}
15         }
16     }
17 
18     return 0;
19 }

http://codeforces.com/contest/1140/problem/C

题意：给定n，k，然后给定 n 对数字 ai，bi。ai 代表一首歌的长度，bi 代表一首歌的幸福值。要求从这 n should歌里面找到不大于 k 首，使得这个歌单的权值最大。

　　　一个歌单的权值是个单种所有歌曲的总长乘以歌单中最小幸福值。

思路：一开始用的就是贪心，按照幸福值从低到高结构体排序，然后枚举，但是WA掉了。最后找到了一个问题，就是没有处理长度这个变量，对于一个已经有的歌单，下一步加入了一个新的幸福值，但是不一定就要抛弃最小的幸福值，应该抛弃的是最小的长度。

　　　所以将队列改成可以排序的优先队列维护歌单就能AC了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct Node{
 5     int L;int H;
 6     friend bool operator<(Node a,Node b){return a.L > b.L;}
 7 }a[300005];
 8 
 9 bool cmp(Node a,Node b){
10     if(a.H == b.H){return a.L < b.L;}
11     return a.H > b.H;
12 }
13 
14 int main()
15 {
16     int n,m;
17     cin >> n >> m;
18     for(int i = 0;i < n;i ++){
19         cin >> a[i].L >> a[i].H;
20     }
21     sort(a,a + n,cmp);
22     priority_queue<Node> Q;
23 //    for(int i = 0;i < n;i ++){
24 //        cout << a[i].L << " " << a[i].H << endl;
25 //    }
26     long long sum = 0;
27     long long ans = 0;
28     for(int i = 0;i < n;i ++){
29         Q.push(a[i]);
30         sum += a[i].L;
31         if(Q.size() > m){
32             sum -= Q.top().L;
33             Q.pop();
34         }
35         //cout << a[i].H << " " << sum <<endl;
36         ans = max(ans,sum * a[i].H);
37     }
38     cout << ans << endl;
39 
40     return 0;
41 }

http://codeforces.com/contest/1140/problem/D

题意：给一个定义为正多边形的权重：在一个正 n 边形内，将所有顶点依次标记为 1,2,3...n 。然后再中间画出 n - 2 条不相交的对角线，那么一个三角形的权重就是三点标记值的乘积，这个多边形的权重就是所有三角形权重的和。求解最小正 n 边形权重。

思路：我认为这题应该是A题。。。只要读懂题就能过。公共顶点一定是 1 ，不断的加上 i * (i + 1) 就行了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 
 5 int main()
 6 {
 7     int n;
 8     cin >> n;
 9     long long ans = 0;
10     for(int i = 2;i <= n - 1;i ++){
11         ans += i * i + i;
12     }
13     cout << ans << endl;
14 
15     return 0;
16 }