考察:贪心+思维
原来是贪心...还以为是dp
思路:
m个已知信息将n个元素序列分成了n+1段.对于每段端点求峰值即可.
但是注意第一天的起点是任意高的.
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int N = 3; 6 int n,m,day[N],h[N],ans; 7 int main() 8 { 9 scanf("%d%d",&n,&m); 10 bool ok = 1; 11 for(int i=1;i<=m;i++) 12 { 13 scanf("%d%d",&day[i&1],&h[i&1]); 14 if(i==1) 15 { 16 ans = max(day[i&1]-1+h[i&1],ans); 17 continue; 18 } 19 if(!ok) continue; 20 int late = day[i&1],pre = day[i-1&1]; 21 if(h[i-1&1]<h[i&1]) 22 { 23 if(day[i-1&1]+h[i&1]-h[i-1&1]>day[i&1]) ok = 0; 24 pre = day[i-1&1]+h[i&1]-h[i-1&1]; 25 }else if(h[i-1&1]>h[i&1]) 26 { 27 int dd =h[i-1&1]-h[i&1]; 28 if(day[i&1]-dd<day[i-1&1]) ok = 0; 29 late = day[i&1]-dd; 30 } 31 int d = late - pre>>1; 32 ans = max(max(h[i&1],h[i-1&1])+d,ans); 33 } 34 int dt = n-day[m&1]; 35 ans = max(ans,h[m&1]+dt); 36 if(ok) printf("%d\n",ans); 37 else puts("IMPOSSIBLE"); 38 return 0; 39 }