题目
分析
- 贪心
- 排序,使跳的保证单调性就好了
- 正解60 分:枚举 正解(不唯一):对于到达的每个点,若要知道应该从哪个点过 来,则要比较从两个不同地方过来的答案进行比较。最后比较式整理 成类似于(f[i] – f[j])/(i – j) > ? 的形式。之后可以将(i, f[i])变为二维上的 一点,比较式就成为了两点间的斜率是否大于一个数。由于 i 是从小 到大枚举的则计算出一个 f[i]时就把它插入到二维平面里,之后只需 维护斜率下降的一段(斜率上升的一段不需要考虑),用栈来存储点, 维护凸包总时间复杂度为 O(n),找最好节点用二分。总时间复杂度为 O(n*log(n))。
代码
1 #include<fstream>
2 #include<algorithm>
3 #define cin fin
4 #define cout fout
5 using namespace std;
6 ifstream fin("game.in");
7 ofstream fout("game.out");
8 struct sb
9 {
10 int val,num;
11 } a[1000001];
12 bool cmp(sb a,sb b)
13 {
14 return a.val>b.val;
15 }
16 int main ()
17 {
18 int n;
19 cin>>n;
20 for (int i=1;i<=n;i++)
21 {
22 cin>>a[i].val;
23 a[i].num=i;
24 }
25 sort(a+1,a+1+n,cmp);
26 int ans=0,now=0;
27 for (int i=1;i<=n;i++)
28 {
29 if (a[i].num>now)
30 {
31 ans+=(a[i].num-now)*a[i].val;
32 now=a[i].num;
33 }
34 }
35 cout<<ans;
36 }