PAT
PAT copied to clipboard
liuchuo
[Advanced/C++/1044] 学姐你好，今天刷到1044道题目的时候发现可以用贪心算法解决，发现时间复杂度可以降低为n
以下是我一些鄙谏，希望学姐能多多指教。 大概就是用i和j的指向位置遍历整个数组，似乎和最小子序列差不多。
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int> dia;
vector<int> diaBegin, diaminBegin;
vector<int> diaEnd, diaminEnd;
int tempmin=99999999;
void findBE(int n,int m){
int i=1,j=i;
int temp=dia[1];
while(j<=n){
if(temp<m){
j++;
temp += dia[j];
}
else if(temp==m){
diaBegin.push_back(i);
diaEnd.push_back(j);
j++;
temp += dia[j];
}else{
if(diaBegin.size()==0){
if(temp-m<tempmin){
if(diaminBegin.size()!=0&& diaminEnd.size()!=0){
diaminBegin.pop_back();
diaminBegin.push_back(i);
diaminEnd.pop_back();
diaminEnd.push_back(j);
tempmin = temp-m;//更新
}else{
diaminBegin.push_back(i);
diaminEnd.push_back(j);
tempmin = temp-m;
}
}else if(temp-m == tempmin){
diaminBegin.push_back(i);
diaminEnd.push_back(j);
}
}
//记录min数组时候，i向后移动一位
temp -= dia[i];
i++;
}
}
}
int main(){
int n,m;
scanf("%d %d",&n, &m);
dia.resize(n+1);
for(int i=1; i<=n; i++){
scanf("%d", &dia[i]);
}
findBE(n,m);
if(diaBegin.size()!=0 && diaEnd.size()!=0){
for(int i=0; i<diaBegin.size(); i++){
printf("%d-%d\n",diaBegin[i],diaEnd[i]);
}
}else{
for(int i=0; i<diaminBegin.size(); i++){
printf("%d-%d\n",diaminBegin[i],diaminEnd[i]);
}
}
return 0;
}
上次的pat成绩考的不太乐观，希望在学姐的博客指导下，快速提高实力。 希望学姐能够多多更新，最好在代码里面多多加一些备注方便理解，有时题目搞不懂一步步调试的时候真是崩溃╯︿╰ 最后祝愿学姐越来越漂亮，越来越聪慧，永远支持学姐（＾-＾）
