題目點我
因為沒有測資，只使用Sample Input測試，答案不一定正確 (不一定能通過測試資料)
第一題:(Time Limit: 3 seconds)
題目輸入:
T (範圍1~20) 有幾輪
N (範圍1~10000) 一輪有幾個digit
digit digit digit ... (範圍 -10000 ~ 10000 )
要求輸出:
最大的連續的digit總和、連續的digit之起始位置、連續的digit之結束位置
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main(int argc, char** argv) {
int times=0;
cin>>times;
while(times>0){
times--;
int len=0;
cin>>len;
int array[len]={0};
for(int i=0;i<len;i++){
cin>>array[i];
}
int max=-10000;//輸入最小有可能為-10000
int start=0,end=0;
for(int i=1;i<=len;i++){//i算有幾個 一連、二連等
for(int j=0;j+i<=len;j++){//j表示從第幾個元素開始計算
int sum=0;
for(int k=1+j;k<=i+j;k++){
sum=sum+array[k-1];
}
cout<<"sum:"<<sum<<endl;
if(max<sum){
max=sum;
start=j+1;
end=start+i-1;
}
}
}
cout<<endl<<"max:"<<max;
cout<<endl<<"start:"<<start;
cout<<endl<<"end:"<<end;
cout<<endl<<endl<<endl;
}
return 0;
}
想不出演算法，只好用暴力來解，但不曉得測資如果是20個10000筆資料，能不能在三秒內完成輸出
第二題:(Time Limit: 3 seconds)
題目輸入:
T (範圍1~10) 有幾輪num1 num2
num1 num2(兩組位數相同(n位數<9)之數字)
num1 num2
num1 num2
...
要求輸出:
最大的連續的digit總和、連續的digit之起始位置、連續的digit之結束位置
想像這是一個有著0、1、2...、8、9的滾輪密碼鎖，
求 從num1到num2 所花費的最少轉動次數?
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main(int argc, char** argv) {
int times=0;
cin>>times;
while(times>0){
times--;
int len=0;
cin>>len;
int array[len]={0};
for(int i=0;i<len;i++){
cin>>array[i];
}
int max=-10000;//輸入最小有可能為-10000
int start=0,end=0;
for(int i=1;i<=len;i++){//i算有幾個 一連、二連等
for(int j=0;j+i<=len;j++){//j表示從第幾個元素開始計算
int sum=0;
for(int k=1+j;k<=i+j;k++){
sum=sum+array[k-1];
}
cout<<"sum:"<<sum<<endl;
if(max<sum){
max=sum;
start=j+1;
end=start+i-1;
}
}
}
cout<<endl<<"max:"<<max;
cout<<endl<<"start:"<<start;
cout<<endl<<"end:"<<end;
cout<<endl<<endl<<endl;
}
return 0;
}
未完待續..(待解中)
創作內容
NCUP 第六屆(2016-07) 練習解題 (用C)
休閒日誌 (0)
